hdoj1272

刺骨的言语ヽ痛彻心扉 2022-08-04 00:41 16阅读 0赞

# 小希的迷宫 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 35731    Accepted Submission(s): 10922**

Problem Description

上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。  
![C20-1007-1.jpg][]

Input

输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。  
整个文件以两个-1结尾。

Output

对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出"Yes"，否则输出"No"。

Sample Input

6 8  5 3  5 2  6 4
    5 6  0 0
    
    8 1  7 3  6 2  8 9  7 5
    7 4  7 8  7 6  0 0
    
    3 8  6 8  6 4
    5 3  5 6  5 2  0 0
    
    -1 -1

Sample Output

Yes
    Yes
    No
      
       
      
       
        
        
      
       
      
       
        
        
      
       
      
       
       
        #include<stdio.h>
    #include<string.h>
    int n,maxx;
    int x[100005],y[100005];
    int pre[100005];
    
    int find(int x){
    	int r=x;
    	while(r!=pre[r])
    		r=pre[r];
    	int i=x,j;
    	if(i!=r){
    		j=pre[i];
    		pre[i]=r;
    		i=j;
    	}
    	return r;
    }
    
    bool join(int x,int y){
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy){
    		if(pre[fy]==fy)
    			pre[fy]=fx;
    		else if(pre[fx]==fx)
    			pre[fx]=fy;
    		else
    			pre[fy]=fx;
    		return true;
    	}
    	return false;
    }
    
    int main(){
    	while(1){
    		int i,j;
    		maxx=0;
    		memset(pre,0,sizeof(pre));
    		for(n=0;;n++){
    			scanf("%d%d",&x[n],&y[n]);
    			pre[x[n]]=x[n];
    			pre[y[n]]=y[n];
    			if(maxx<x[n])
    				maxx=x[n];
    			if(maxx<y[n])
    				maxx=y[n];
    			if((x[n]==-1&&y[n]==-1)||(x[n]==0&&y[n]==0))
    			break;
    		}
    		if(x[n]==-1&&y[n]==-1) break;
    			n-=1;
    		int ka=0;
    		for(i=0;i<=n;i++)
    			if(join(x[i],y[i]))
    				ka++;
    		if(ka<n+1)
    			printf("No\n");
    		else{
    			int kk=0;
    			for(i=0;i<maxx;i++)
    				if(pre[i]&&pre[i]==i)
    					kk++;
    			if(kk>1)
    				printf("No\n");
    			else
    				printf("Yes\n");
    		}
    			
    			
    	}
    	return 0;
    }

[C20-1007-1.jpg]: /images/20220731/1076233f61774208bac4a200702d3718.png