Problem : 1272 ( 小希的迷宫 ) Judge Status : AcceptedRunId : 5995331 Language : C++ Author : qq1203456195Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <iostream>
5 using namespace std;
6 #define N 101000
7 #define max(a,b) ((a)>(b))?(a):(b)
8 int number[N];
9 int set[N];
10 int Find(
int x)
11 {
12 int r=
x,i,j;
13 while (
set[r]!=
r)
14 r=
set[r];
15 i=
x;
16 while (
set[i]!=r)
//i的父亲不是r,进行压缩
17 {
18 j=
set[i];
//记录i的父亲
19 set[i]=r;
//改变i的父亲
20 i=j;
//判断i的父亲
21 }
22 return r;
23 }
24 void Merge(
int x,
int y)
25 {
26 int a,b;
27 a=
Find(x);
28 b=
Find(y);
29 set[a]=
b;
30 }
31 int main()
32 {
33 int i,x,y,sets,lines,points,n;
34 while (scanf(
"%d%d",&x,&y),~x||~
y)
35 {
36 //初始化
37 n=
0;
38 lines=
0;
39 sets=
0;
40 points=
0;
41 for(i=
0;i<N;i++
)
42 {
43 number[i]=
0;
44 set[i]=
i;
45 }
46 //构造
47 while (x||
y)
48 {
49 n=
max(x,n);
50 n=
max(y,n);
51 number[x]=
1;
52 number[y]=
1;
53 lines++
;
54 Merge(x,y);
55 scanf(
"%d%d",&x,&
y);
56 }
57 //统计
58 for (i=
1;i<=n;i++
)
59 {
60 if(number[i]==
1)
61 {
62 points++
;
63 if(
set[i]==i) sets++
;
64 }
65 }
66 //分析[注意n为0的情况]
67 if((sets==
1&&points==lines+
1)||(points==
0))
68 printf(
"Yes\n");
69 else
70 printf(
"No\n");
71 }
72 return 0;
73 }
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/25/2518639.html
相关资源：数据结构—成绩单生成器
