P1859 -- 建桥

时间限制：1000MS

内存限制：131072KB

Description

在弹幕战完美结束之后，有趣张立马回到了房地产的大业中~因为他曾经和华莱士谈笑风生过，所以他毫不费力地弄到了一片群岛。

可是这片群岛上的一个个岛屿是孤立的。为了能在岛屿间快速地通行，并且方便泡到各个岛屿上的妹纸，有趣张决定在岛屿之间修建大桥（虽然有时候桥的面积比岛还大但是有趣张肯定不稀罕这点钱对吧）。有时候他会把2个岛屿之间连接起来（连接起来的意思就是说这两个岛屿可以通过这座桥直接互相到达）有时候为了更好地规划他需要知道岛屿之间是否是连通的，也就是说能不能从一个岛屿通过走某些桥到达另一个岛屿。所以他就把调查岛屿是否连通的任务交给了你。

Input Format

输入第一行是两个整数N,M（1 <= N,M <= 200000），N表示有多少个岛屿,M表示他做了多少事.接 下来的M行中，每行包含三个整数T,A,B，如果T=1,那么表示他把标号为A和B的岛屿用桥梁连接起来.如果T=2,那么他表示想知道,标号为A和B的岛屿是否是连通的.

Output Format

输出包括若干行.输入文件每出现一个T=2的操作,输入一行.如果A和B是连通的,那么输出Yes,否则输出No.（注意大小写）

Sample Input

4 52 1 31 1 32 1 31 3 42 1 4

Sample Output

NoYesYes

Hint

对于20％的数据，保证有n,m<=100；

对于30％的数据，保证有n,m<=1000；

对于全部的数据，保证有n,m<=200000。

 

【题解】 基本的并查集，但是要路径压缩，没有路径压缩会T三个点，所以，路径压缩还是很重要滴。

因为懒就没去写按秩优化了……

1 #include
       
         2 using namespace std; 3 int pre[200001]; 4 int findset(int x) { 5     int r,i,j; 6     r=i=x; 7     while(r!=pre[r]) r=pre[r]; 8     while(i!=r) { 9         j=pre[i];10         pre[i]=r;11         i=j;12     }13     return r;14 }15 void join(int a,int b) {16     int a1=findset(a),b1=findset(b);17     if(a1!=b1) pre[a1]=b1;18 }19 int main() {20     int n,m;21     scanf("%d%d",&n,&m);22     for (int i=1;i<=n;++i) pre[i]=i;23     while(m--) {24         int t,a,b;25         scanf("%d%d%d",&t,&a,&b);26         if (t==2) {27             int x=findset(a),y=findset(b);28             if(x==y) printf("Yes\n");29             else printf("No\n");30         }    31         if (t==1) join(a,b);32     }33     return 0;34 }