Codeforces Round #541 (Div. 2) F. Asya And Kittens(并查集+邻接表)

题目链接：https://codeforces.com/contest/1131/problem/F

       题意是有n个数，有n-1种关系，最终会构成一颗树，从根节点按顺序输出这n个点，其实看图就理解的差不多了。

       思路就是按题意将所要连的两个链表merge一下就好了，不太好描述，看代码画画图就理解了。

---

AC代码：

代码语言：javascript复制

#include <bits/stdc  .h>
#define maxn 150005
using namespace std;
int pre[maxn];
int n;
vector<int> v[maxn];

void init(){
  for(int i=0;i<=n;i  ){
    pre[i] = i;
  }
}

void dfs(int x){
  printf("%d ", x);
  for(int i=0;i<v[x].size();i  ) dfs(v[x][i]);
}

int Find(int x){
  if(x != pre[x]){
    pre[x] = Find(pre[x]);
  }
  return pre[x];
}

void merge(int x,int y){
  int fx = Find(x);
  int fy = Find(y);
  if(fx != fy){
    pre[fy] = fx;
    v[fx].push_back(fy);
  }
}

int main()
{
  scanf("%d",&n);
  init();
  for(int i=1;i<n;i  ){
    int u, v;
    scanf("%d%d",&u, &v);
    merge(u, v);
  }
  dfs(Find(1));
  return 0;
}

merge 链表

0 人点赞