nyoj 20

阳光穿透心脏的1/2处 2022-08-17 14:26 80阅读 0赞

/\*\*吝啬的国度  
时间限制：1000 ms | 内存限制：65535 KB  
难度：3  
描述  
在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，  
他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重  
复的路）。  
输入  
第一行输入一个整数M表示测试数据共有M(1<=M<=5)组  
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示城市的总个  
数，S表示参观者所在城市的编号  
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。  
输出  
每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。  
（其中i=S时，请输出-1）  
样例输入  
2  
10 1  
1 9  
1 8  
8 10  
10 3  
8 6  
1 2  
10 4  
9 5  
3 7

1  
10 7  
1 9  
1 8  
8 10  
10 3  
8 6  
1 2  
10 4  
9 5  
3 7  
样例输出  
\-1 1 10 10 9 8 3 1 1 8\*/

“这N个城市间只有N-1条路把这个N个城市连接起来”,说明这是一个连通图，而边数等于顶点数 - 1的连通图就是一棵树

注意每次输入时要把图的邻接表清0，不然会有wa

#include <cstdio>
    #include <vector>
    #include <cstring>
    #include <iostream>
    using namespace std;
    
    int N,S,T;
    const int SIZE = 100010;
    vector<int>G[SIZE];
    int res[SIZE];
    
    void Output(){
        vector<int>::iterator it;
        for(int i=1;i<=N;i++){
       //有1~N个顶点，
            cout << i << ": ";
            for(it=G[i].begin();it!=G[i].end();it++) cout << *it << " ";
            cout << endl;
        }
        return ;
    }
    
    void dfs(int cur){
        vector<int>::iterator it;
        int nex;
        //父子节点关系
        for(it=G[cur].begin();it!=G[cur].end();it++){
            nex = *it;
            if(!res[nex]){
                res[nex] = cur;
                dfs(nex);
            }
        }
        return ;
    }
    
    int main(){
        int M,a,b;
        while(~scanf("%d",&M)){
            while(M--){
                memset(G,0,sizeof(G));//邻接表初始化清0
                scanf("%d %d",&N,&S);
                for(int i=1;i<N;i++){
       //N-1条边
                    scanf("%d %d",&a,&b);
                    G[a].push_back(b);//无向图
                    G[b].push_back(a);
                }
                //Output();
                memset(res,0,sizeof(res));
                dfs(S);
                res[S] = -1;
                for(int i=1;i<=N;i++){
                    cout << res[i];
                    cout << " ";
                    //if(i!=N) cout << " ";
                }
            }
        }
    
        return 0;
    }