时空限制: 1000ms,128M
数据规模:
对于 30% 的数据, N<=10,M<=20;
对于 70% 的数据, N<=100,M<=1000;
对于 100% 的数据, N<=10000,M<=200000.
模板题, 我还要讲什么呢......
- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- #pragma GCC optimize(2)
- #pragma GCC optimize(3)
- using namespace std;
- int n,m;
- int father[10005];
- inline int read(){
- int s=0,w=1;
- char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
- while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
- return s*w;
- }
- /*int find(int x){
- while(x!=father[x]){
- x=father[x];
- }
- return x;
- }*/
- int find(int p){
- if(father[p]==p){
- return p;
- }
- return father[p]=find(father[p]);
- }
- void C(int a,int b){
- int fa=find(a);
- int fb=find(b);
- /*if(fa!=fb)
- {
- father[fa]=fb;
- }*/
- father[fa]=fb;
- }
- int main(){
- n=read();
- m=read();
- for(int k=1;k<=n;k++){
- father[k]=k;
- }
- while(m--){
- int z,x,y;
- z=read();
- x=read();
- y=read();
- if(z==1){
- C(x,y);
- }
- else{
- int i=find(x);
- int j=find(y);
- if(i!=j){
- printf("N\n");
- }
- else{
- printf("Y\n");
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3112561.html