题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=42
题目分析:
要能一笔画化成需要同时满足两个以下条件:
1)该图是连通的。
2)图中奇点的个数是2或者0。
参考代码:
#include<stdio.h> #include<string.h> int set[1001]; int find(int k) { int r = set[k]; while(r != set[r]) r = set[r]; return r; } void merge(int r1, int r2) { if(r1 < r2) set[r2] = r1; else set[r1] = r2; } int main() { bool used[1001]; int count[1001]; int t,i; int a,b,c; int p,q; int r1,r2; int ans; scanf("%d", &t); while(t--) { memset(count, 0, sizeof(count)); memset(used, 0, sizeof(used)); scanf("%d %d", &p, &q); for(i = 0; i <= q; ++i) set[i] = i; c = 0; for(i = 0; i < q; ++i) { scanf("%d %d", &a, &b); if(!used[a]) { ++c; used[a] = true; } if(!used[b]) { ++c; used[b] = true; } r1 = find(a); r2 = find(b); if(r1 != r2) { merge(r1,r2); --c; } ++count[a]; ++count[b]; } ans = 0; for(i = 1; i <= p; ++i) { if(!used[i]) ++c; if(count[i] & 1) ++ans; } if(c <= 1 && (ans == 2 || ans == 0)) printf("Yes\n"); else printf("No\n"); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)