【DFS,雙向】NYOJ-20-吝嗇的國度 -开发者知识库

【DFS,雙向】NYOJ-20-吝嗇的國度 -开发者知识库,第1张

【題目鏈接:NYOJ-20

  很巧妙,要好好想想

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector<int>a[100005];
int b[100005],n,s;
void dfs(int x,int y){
    for (int i = 0; i <a[x].size();i  )
        if (a[x][i] != y)
            dfs(a[x][i],b[a[x][i]]=x);
        return;
}
int main(){
    int M,x,y;
    scanf("%d",&M);
    while (M--){
        scanf("%d%d",&n,&s);
        for (int i = 1; i <n; i  ){
            a[i].clear();
        }
        for (int i = 1; i <n; i  ){
            scanf("%d%d",&x,&y);
            a[x].push_back(y); //相當二維數組 
            a[y].push_back(x);
        }
        b[s] = -1;//與S相等則為-1  
        dfs(s,-1);
        for (int i = 1; i <= n; i  )
            printf("%d ",b[i]);
        printf("\n");
    }
    return 0;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复