# 小希的迷宫

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 21080    Accepted Submission(s): 6449

Problem Description

Input

Output

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

```  1 #include<iostream>
2 #include<vector>
3 #include<cstdio>
4 #include<cstring>
5 #include<cstdlib>
6 using namespace std;
7 const int maxn=100001;
8 int father[maxn+2],rank[maxn+2];
9 struct nod
10 {
11     nod(int m,int n):a(m),b(n){};
12     int a,b;
13 };
14 void init(int n)
15 {
16    for(int i=1;i<=n;i++)
17    {
18        father[i]=i;
19        rank[i]=1;
20    }
21 }
22 int setfind(int x)
23 {
24     /*如果root不为自己，那就去找最原始的root*/
25     if(x!=father[x])
26     {
27         father[x]=setfind(father[x]);
28     }
29     return father[x];
30 }
31 void collect(int x, int y)
32 {
33     x=setfind(x);
34     y=setfind(y);
35     if(x!=y)
36     {
37      if(rank[x]>rank[y])
38       {
39           father[y]=x;
40           rank[x]+=rank[y];
41       }
42       else
43       {
44           father[x]=y;
45           rank[y]+=rank[x];
46       }
47     }
48 }
49
50 int main()
51 {
52     int a,b,max,i;
53     /*freopen("test.in","r",stdin);*/
54     while(1)
55     {
56         vector<nod>sa;
57         max=0;
58        scanf("%d%d",&a,&b);
59        if(a==-1&&b==-1)
60                return 0;
61        while(a+b)
62        {
63            int temp=a>b?a:b;
64              if(max<temp)
65                  max=temp;
66              nod str(a,b);
67              sa.push_back(str);
68          scanf("%d%d",&a,&b);
69        }
70        int len=sa.size();
71        if(len==0)
72        {
73            puts("Yes");
74            continue;
75        }
76        init(max);
77        vector<nod>::iterator it;
78       for(it=sa.begin();it!=sa.end();it++)
79       {
80           /*printf("%d%d",(*it).a,it->b);*/
81             collect((*it).a,it->b);
82       }
83        int anst=0,pos,ansa=0;
84
85       for( i=1;i<=max;i++)
86       {
87         /*  printf("%d",father[i]);*/
88           if(anst<rank[i])
89           {
90               anst=rank[i];
91               pos=i;    /*确定root*/
92           }
93           if(father[i]!=i)
94               ansa++;
95       }
96       if(anst==ansa+1)   /*是一棵树*/
97       {
98           bool tag=true;
99           for(i=1;i<=max;i++)
100           {
101               /*是否有循环的树*/
102               if(father[i]!=pos&&father[i]!=i)
103               {
104                   tag=false;
105                   break;
106               }
107           }
108           if(tag)
109                 printf("No\n");
110               else
111                 printf("Yes\n");
112       }
113       else
114           printf("No\n");
115     }
116     return 0;
117 }```

657 篇文章64 人订阅

0 条评论

## 相关文章

15730

85630

360130

### Java数据结构和算法（一）——简介

本系列博客我们将学习数据结构和算法，为什么要学习数据结构和算法，这里我举个简单的例子。 　　编程好比是一辆汽车，而数据结构和算法是汽车内部的变速箱。一个开车...

32990

29350

34050

29990

56570

36550

### Leetcode 22 Generate Parentheses 搜索与DP的纠结

Given n pairs of parentheses, write a function to generate all combinations of ...

25290