NYOJ 42 一筆畫問題
描述
zyc從小就比較喜歡玩一些小游戲，其中就包括畫一筆畫，他想請你幫他寫一個程序，判斷一個圖是否能夠用一筆畫下來。
規定，所有的邊都只能畫一次，不能重復畫。
輸入
第一行只有一個正整數N(N<=10)表示測試數據的組數。
每組測試數據的第一行有兩個正整數P,Q(P<=1000,Q<=2000)，分別表示這個畫中有多少個頂點和多少條連線。（點的編號從1到P）
隨後的Q行，每行有兩個正整數A,B(0<A,B<P)，表示編號為A和B的兩點之間有連線。
輸出
如果存在符合條件的連線，則輸出"Yes",
如果不存在符合條件的連線，輸出"No"。
樣例輸入
2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
1 3
1 4
3 4
樣例輸出
No
Yes
本題來自：http://acm.nyist.net/JudgeOnline/problem.php?pid=42
問題分析：
歐拉定理 如果一個網絡是連通的並且奇頂點的個數等於0或2，那麼它可以一筆畫出；否則它不可以一筆畫出。
判斷一筆畫的方法：
①是連通的。一個圖，如果圖上任意二點總有線段連接著，就稱為連通的。不是連通的就不能一筆畫出。
②奇點個數是0或者是2。圖上線段的端點可以分成二類，奇點和偶數。一個點，以它為端點的線段數是奇數就稱為奇點，線段數是偶數就稱為偶點。
一個圖是否是一筆畫就看奇點的個數，奇點個數是 0 或者 2，就是一筆畫，否則就不是一筆畫。
所以這個問題完全可以轉化策略為：
第一步： 首先我們不管它三七二十幾，先進行連通性的判斷。
第二步：
（1）如果是連通的，我們來判斷此圖的度的奇點的個數是0或者是2 ，如果是，則說明這個是歐拉圖，即可以一筆畫出，反之則不能一筆畫出
（2）如果是非連通的，這說明這個圖很定不能一筆畫出。
代碼一：——深搜
復制代碼
1 #include <stdio.h>
2 #include <string.h>
3 int P,Q;
4 int bian[1005];
5 bool map[1005][1005],vis[1005];
6 void dfs(int cur)
7 {
8 vis[cur]=true;
9 for(int i=1;i<=P;i++)
10 if(map[cur][i])
11 {
12 bian[cur]++;
13 if(!vis[i])
14 dfs(i);
15 }
16 }
17
18 int main()
19 {
20 int T;
21 scanf("%d",&T);
22 while(T--)
23 {
24 int ok=1;
25 memset(map,false,sizeof(map));
26 memset(vis,false,sizeof(vis));
27 memset(bian,0,sizeof(bian));
28
29 scanf("%d%d",&P,&Q);
30
31 for(int i=0;i<Q;i++)
32 {
33 int A,B;
34 scanf("%d%d",&A,&B);
35 map[A][B]=true,map[B][A]=true;
36 }
37
38 dfs(1); // 判斷是否連通的，如果vis有個false，就不是連通的
39
40 for(int i=1;i<=P;i++)
41 if(!vis[i])
42 {
43 ok=0;
44 break;
45 }
46
47 if(!ok)printf("No\n");
48 else
49 {
50 int xx=0;
51 for(int i=1;i<=P;i++)
52 if(bian[i]%2)xx++;
53 if(xx==0||xx==2)printf("Yes\n");
54 else printf("No\n");
55 }
56 }
57 return 0;
58 }
復制代碼
在AC後，網上看到別人的思路，還有一種方法來判斷連通性——並查集。
並查集資料：http://www.cnblogs.com/cyjb/p/UnionFindSets.html
代碼二：——並查集
復制代碼
1 //並查
2 #include<stdio.h>
3 #include<string.h>
4 int father[1010],ans[1010];
5 void init()
6 {
7 for(int i=0;i<1010;i++)
8 father[i]=i;
9 }
10 int find(int x)
11 {
12 if(father[x]==x)
13 return x;
14 else
15 return father[x]=find(father[x]);
16 }
17 int main()
18 {
19 int ncases,n,m,x,y,count,jdcount;
20 scanf("%d",&ncases);
21 while(ncases--)
22 {
23 memset(ans,0,sizeof(ans));
24 init();
25 count=jdcount=0;
26 scanf("%d %d",&n,&m);
27 for(int i=1;i<=m;i++)
28 {
29 scanf("%d %d",&x,&y);
30 ans[x]++; ans[y]++;
31 x=find(x); y=find(y);
32 if(x!=y)
33 father[x]=father[y];
34 }
35
36 for(i=1;i<=n;i++)
37 if(find(i)==i)
38 count++;
39 for(i=1;i<=n;i++)
40 if(ans[i]%2==1)
41 jdcount++;
42 if((jdcount==0||jdcount==2)&&count==1)
43 printf("Yes\n");
44 else
45 printf("No\n");
46 }
