ACM_城市交通线（简单并查集）

Problem Description:

A国有n座城市，编号为1~n，这n个城市之间没有任何交通线路，所以不同城市的居民之间不能互通，所以A国的人打算为这n个城市建立k条交通线（两座城市之间可以有两条及以上的线路），交通线只能贯穿两座城市p, q（存在p=q的情况，不用考虑但会占用一条交通线）, 建立交通线后两座城市的居民可以互通。例如：建立1, 4后再建立4, 2，则1和2是互通的（1—>4—>2）。建立完k条交通线后，接着有m次询问，问居住在两个城市a, b的居民能否互通。

Input:

输入数据有多组，每一组的第一行包含两个整数n (0<n<=5000）, k (0<k<=10000) , 接下来有k行，每行包含两个整数p，q (0<p,q<=n)，代表城市p，q之间建立一条交通线。再接着一个整数m (0<m<=n) 代表有m次询问，接下来有m行，每行包含两个整数a, b(0<a,b<=n) 询问城市a,b之间的居民能否互通 (同一个城市的居民能互通)。

Output:

两座城市的居民可以互通则输出“YES”，否则输出“NO”，每个输出占一行。

Sample Input:

Sample Output:

YES

NO

NO

YES
解题思路：简单的并查集，水过。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int n,k,p,q,m,a,b,fa[maxn];

 int findt(int x){

     int pir=x,tmp;

     while(pir!=fa[pir])pir=fa[pir];

     while(x!=pir){tmp=fa[x];fa[x]=pir;x=tmp;}//路径压缩

     return x;

 }

 void unite(int x,int y){

     x=findt(x);y=findt(y);

     if(x!=y)fa[x]=y;

 }

 int main(){

     while(~scanf("%d%d",&n,&k)){

         for(int i=;i<=n;++i)fa[i]=i;

         while(k--){scanf("%d%d",&p,&q);unite(p,q);}

         scanf("%d",&m);

         while(m--){

             scanf("%d%d",&a,&b);

             if(findt(a)==findt(b))puts("YES");

             else puts("NO");

         }

     }

     return ;

 }

巴特西