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

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

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

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


AC代码:

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券