（判环-基础并查集）hdu1272 小希的迷宫

朱雀 2022-04-16 07:17 127阅读 0赞

传送门：[hdu1272 小希的迷宫][hdu1272]

**目录**

错误代码：

正确代码：

--------------------

判断是否能形成环即可。代码wa，还没找出错QWQ。-------找出错误了。

错在连通分量只能有一个，如果连通分量大于1，输出no。

### 错误代码： ###

//错误代码：
    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn=100010;
    int par[maxn];
    bool flag;
    
    void init(){
    	flag=true;
    	for(int i=1;i<maxn;i++)
    		par[i]=i;
    }
    
    int fi(int x){
    	if(par[x]==x) return x;
    	return par[x]=fi(par[x]); 
    }
    
    void join(int x,int y){
    	int fx=fi(x),fy=fi(y);
    	if(fx==fy) flag=false;
    	else par[fy]=fx;
    }
    
    int main(){
    	int a,b;
    	init();
    	while(~scanf("%d%d",&a,&b)){
    		if(a==-1&&b==-1) break;
    		if(a==0&&b==0){
    			if(flag) printf("Yes\n");
    			else printf("No\n");
    			init();
    			continue;
    		}
    		join(a,b);
    	}
    	return 0;
    }

### 正确代码：  ###

//正确代码：
    #include<iostream>
    #include<cstdio>
    #include<set>
    using namespace std;
    const int maxn=100010;
    int par[maxn];
    bool flag;
    
    void init(){
        flag=true;
        for(int i=1;i<maxn;i++)
            par[i]=i;
    }
    
    
    int fi(int x){
        if(par[x]==x) return x;
        return par[x]=fi(par[x]); 
    }
    
    /*
    int fi(int x){
        int r=x;
        while(par[r]!=r) r=par[r];
        int tmp,j=x;
        while(par[j]!=r){
            tmp=j;
            par[j]=r;
            j=par[tmp];
        }
        return r;
    }
    */
    
    void join(int x,int y){
        int fx=fi(x),fy=fi(y);
        if(fx==fy) flag=false;
        else par[fy]=fx;
    }
    
    
    int main(){
        int a,b;
        init();
        set<int> s;
        while(~scanf("%d%d",&a,&b)){
            if(a==-1&&b==-1) break;
            if(a==0&&b==0){
                if(flag){
                    int cnt=0;
                    set<int>::iterator it;
                    for(it=s.begin();it!=s.end();it++){
                        if(par[*it]==*it){
                            cnt++;
                            if(cnt>1){
                                flag=false;
                                break;
                            }
                        }
                    }
                }
                s.clear();
                if(flag) printf("Yes\n");
                else printf("No\n");
                init();
                continue;
            }
            s.insert(a);
            s.insert(b);
            join(a,b);
        }
        return 0;
    }

[hdu1272]: http://acm.hdu.edu.cn/showproblem.php?pid=1272