Xiao Xie's Labyrinth HDU-1272

What does the writing of the function in this question reflect compared to a common union set?

Specific problems specific analysis is the living soul of Marxism

But the root is still a collection.
Thousands of waistcoats belong to

As for what to pay attention to......
Do you know how I spent the night?!!

Lazy to cut the input method was annotated in English for the purpose of tuning.

Description

Last time Gardon had a long time at the Labyrinth Castle (see Problem B), now she wants to design a labyrinth for Gardon to walk. But she has a different way of thinking about designing the labyrinth. First of all, she thinks all the channels should be two-way connected. That is, if there is one channel connecting room A and B, she can either walk from room A to room B or from room B to room A through it. To make it more difficult, Xiao Xie wants any two rooms to have and only one path to connect. (unless you go back). Xiao Xie gives you her design now to help you decide if her design meets her design ideas. For example, the first two are qualified, but the last one has two ways from 5 to 8.

When you read this, Bullman should find three pits:
1. And find rings
2. Statistical Root Nodes
3. Compare disgusting set input (for beginners like me)
Later, however, there's one more point in the dalao puzzle when it comes to typing 0 directly.
This I am not aware of anyway

Input

The input contains multiple sets of data, each of which is a 0-ending list of integer pairs representing the number of two rooms connected by a channel. The room number is at least 1 and does not exceed 100000. There is a blank line between each set of data.
The entire file ends with two-1.

Output

For each set of data entered, the output only includes one line. If the labyrinth fits the mindset of a little thought, output "Yes", otherwise output "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

This harvest is mainly about learning and collecting rings
Also! Code capabilities improved!
The normal union function is void (in my mind)
This can be used to represent and set a ring by Boolean return values.
BEAUTIFUL
By the way, do while should be less

```#include<iostream>
using namespace std;
int fa[10000500],a,b,tot;
bool vis[10000500],flag;
void init(){
for(int i=1;i<=1000000;i++){//initialization
fa[i]=i;
vis[i]=0;
}
}
int find(int x){//an usual find(x)
if(fa[x]==x) return x;
else{
fa[x]=find(fa[x]);
return fa[x];
}
//while(x!=fa[x])
//    x=fa[x];
//return x;
}
bool unin(int x,int y){//pay attention to circles
int rx=find(x);//i mean all points can only connect once
int ry=find(y);//or there may be circles
if(rx!=ry){
fa[rx]=ry;
return true;
}//if some point is connecting more than once
else return false;//return false
}
int main(){
int cnt=0;
while(1){
cnt=0;
flag=1;
init();
do{//consider inputting 0 0 in the begginning
cnt++;
if(cnt==1) cin>>a>>b;
if(a==-1&&b==-1) return 0;
if(a==0&&b==0){
cout<<"Yes"<<endl;
continue;
}
vis[a]=1;vis[b]=1;//i have visited a and b
if(unin(a,b)==false) flag=false;
}while(cin>>a>>b&&a!=0&&b!=0);//do while MUST be designed for this
//beautiful
if(flag==false)cout<<"No"<<endl;
else{
tot=0;
for(int i=1;i<=1000000;i++){
if(vis[i]&&fa[i]==i){//they may jump over some numbers
tot++;//how many father points?
}
}
if(tot==1)cout<<"Yes"<<endl;//if there is only one fa
//then the DAG is the one we want
else cout<<"No"<<endl;
}
}
return 0;
}
```

Keywords: Union Find

Added by phillips321 on Sat, 27 Nov 2021 19:27:19 +0200