题解 | #旅游# 三种图的遍历方式

由于路径比节点少，说明没有环，可以认为是树

其实就是树（图）的根必须选版最大独立集问题。。。

因为对图的储存和遍历不是很熟悉，就把三个方法都实现了一遍。

这题真的是medium吗，最大独立集是经典问题没错，可是性能限制真的好严格。

用拉链表连递归和std栈都不敢用，手写循环和栈勉强通过，用链式前向星才能稳过，怎么看也是hard吧！

临接矩阵

通过率9/20，测了下数据量到五万，在创建数组那一步如果用原生数组会栈溢出，用vector会内存超限。除非是很密集的图（比如边数接近n平方的有向图）基本上可以放弃这个方法了。

#include <any>
#include <climits>
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
 
int main() {
    int n,cur,first,t1,t2,i,j,top,root;
    cin>>n>>first;
    first--;//转下标
    //cout<<n<<' '<<cur<<endl;
    bool neighbor[n][n];
    for(i=0;i<n;++i)for(j=0;j<n;++j)neighbor[i][j]=false;
    int dp[n][2];
    //由于路径比节点少，说明没有环，可以认为是树
    //由于是无向的，亲子不分，所以只能记录已经走过的节点
    bool visited[n];
    for(i=0;i<n;++i)visited[i]=false;
    int post_order[n+1],st[n];//本来应该用栈，n已知，可以用数组预分配内存
 
    for(i=1;i<n;++i){
        //n-1条路径
        cin>>t1>>t2;
        t1--;t2--;
        neighbor[t1][t2]=true;
        neighbor[t2][t1]=true;
    }
 
  // for(i=0;i<n;++i)for(j=0;j<n;++j)cout<<neighbor[i][j];
    //构建后续遍历
     i=n-1;top=0; st[0]=first;
 
     while(top>=0){
        cur=st[top];
        --top;
        visited[cur]=true;
        post_order[i]=cur;
        --i;
        //cout<<cur<<endl;
        for(j=0;j<n;++j){
            if(visited[j]){continue;}
            if(neighbor[cur][j]){
                top++;
                st[top]=j;
            }
        }
    }
 
    for(i=0;i<n;++i)visited[i]=false;
    post_order[n]=INT_MAX;
    for(i=0;i<n;++i){
        cur=post_order[i];
        //cout<<cur<<endl;
        dp[cur][1]=1;
        dp[cur][0]=0;
        for(j=0;j<n;++j){
            if(!visited[j]){
                //cout<<neighbor[cur][j]<<"未定义"<<endl;
                continue;}
            if(neighbor[cur][j]){
                 dp[cur][1]+=dp[j][0];
                    dp[cur][0]+=max(dp[j][0],dp[j][1]);//注意这里，未选情况下子可选可不选，不要被惯性思维误导选了
            }
           
        }
       // cout<<dp[cur][0]<<' '<<dp[cur][1]<<endl;
        visited[cur]=true;
        //cout<<cur<<' '<<dp[cur][0]<<' '<< dp[cur][1]<<endl;
       
    }
    cout<<dp[first][1]<<endl;
   
 
}
// 64 位输出请用 printf("%lld")

邻接表（拉链表）

要创建n个动态数组，内存使用效率略逊于链式前向星。

最复杂用例性能

最简单用例性能

stack容器性能很差，既然最大长度已知，这里用数组实现了栈的功能，如果用std的栈用例通不过。

遍历用的循环法，如果用递归估计也通不过用例（悲）

很极限地全ac了，一共一百个人刷题排九十多。

#include <any>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n,cur,first,t1,t2,i,j,top,root;
    cin>>n>>first;
    first--;//转下标
    //cout<<n<<' '<<cur<<endl;
    vector<int> neighbor[n];
    int dp[n][2];
    //由于是无向的，亲子不分，所以只能记录已经走过的节点
    bool visited[n];
    for(i=0;i<n;++i)visited[i]=false;
    int post_order[n+1],st[n];//本来应该用栈，n已知，可以用数组预分配内存
 
    for(i=1;i<n;++i){
        //n-1条路径
        cin>>t1>>t2;
        t1--;t2--;
        neighbor[t1].push_back(t2);
        neighbor[t2].push_back(t1);
    }
 
 
    //构建后续遍历,两种方法，都需要多出一个数组储存
     i=n-1;top=0; st[0]=first;
 
     while(top>=0){
        cur=st[top];
        --top;
        visited[cur]=true;
        post_order[i]=cur;
        --i;
        for(j=0;j<neighbor[cur].size();++j){
            if(visited[neighbor[cur][j]])continue;
            top++;
            st[top]=neighbor[cur][j];
        }
    }
 
    for(i=0;i<n;++i)visited[i]=false;
    post_order[n]=INT_MAX;
    for(i=0;i<n;++i){
        cur=post_order[i];
        dp[cur][1]=1;
        dp[cur][0]=0;
        for(j=0;j<neighbor[post_order[i]].size();++j){
            if(!visited[neighbor[cur][j]]){
                //cout<<neighbor[cur][j]<<"未定义"<<endl;
                continue;}
            dp[cur][1]+=dp[neighbor[cur][j]][0];
            dp[cur][0]+=max(dp[neighbor[cur][j]][0],dp[neighbor[cur][j]][1]);//注意这里，未选情况下子可选可不选，不要被惯性思维误导选了
             
        }
        visited[cur]=true;
        //cout<<cur<<' '<<dp[cur][0]<<' '<< dp[cur][1]<<endl;
       
    }
    cout<<dp[first][1]<<endl;//出发点一定要选
   
 
}
// 64 位输出请用 printf("%lld")

链式前向星

我再研究下循环法怎么写（。）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+1000;
int n,s,f[N][2];
int ver[N],nxt[N],head[N],tot;
inline void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
inline void dfs(int x,int fa)
{
    f[x][1]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        f[x][1]+=f[y][0];
        f[x][0]+=max(f[y][0],f[y][1]);
    }
}
int main()
{
    cin>>n>>s;
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(s,0);
   cout<<f[s][1]<<endl;
    return 0;
}