cf-Round541-Div2-F（并查集+静态链表）

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

思路：

很容易看出这是一道并查集的题目，因为要输出每个cage中住的鸟的编号，故采用静态链表。用l[i]表示一条链的最左端编号，r[i]表示一条链最右端编号，nex[i]表示编号i后面的鸟的编号，root[i]表示i的祖先，剩下套并查集模板即可。我在这CE了两次，后来问了大神才找到错误，bits/stdc++中已经1定义了get，next，而我的程序中将这两个作为变量，从而CE，但可能是我的编译器的标准库的问题，使得本地可以通过。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int n,x,y;

 int l[maxn],r[maxn],nex[maxn],root[maxn];

 int getr(int k){

     if(root[k]==k) return k;

     else return root[k]=getr(root[k]);

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;++i)

         l[i]=i,r[i]=i,root[i]=i;

     n--;

     while(n--){

         scanf("%d%d",&x,&y);

         int rx=getr(x),ry=getr(y);

         root[ry]=rx;

         nex[r[rx]]=l[ry];

         r[rx]=r[ry];

     }

     int p=l[getr()];

     while(p){

         printf("%d ",p);

         p=nex[p];

     }

     printf("\n");

     return ;

 }

巴特西

cf-Round541-Div2-F（并查集+静态链表）

最新文章

热门文章