时间限制:3000 ms | 内存限制:65535 KB
难度:4
描述
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
来源[张云聪]原创
做这道题之前,我们先引入一个列题........
在18世纪的哥尼斯堡城里有七座桥。当时 有很多人想要一次走遍七座桥,并且每座桥只能经过一次。这就是世界上很有名的哥尼斯堡七桥问题。你能一次走遍这七座桥,而又不重复吗?(自己动手画画吧) 答案 16.一笔画问题 这个问题,实际上是一笔画问题。 一笔画就是一笔可以画成一个图。 判断一笔画的方法: ①是连通的。一个图,如果图上任意二点总有线段连接着,就称为连通的。不是连通的就不能一笔画出。 ②奇点个数是0或者是2。图上线段的端点可以分成二类,奇点和偶数。一个点,以它为端点的线段数是奇数就称为奇点,线段数是偶数就称为偶点。 一个图是否是一笔画就看奇点的个数,奇点个数是 0 或者 2,就是一笔画,否则就不是一笔画。 哥尼斯桥问题,就是一笔画问题。但因A、B、C、D四个点都是奇点即奇点的个数是4,而不是0或2,所以不是一笔画,也就不能一次走遍,而又不重复。 |
---|
针对这么个情况,所谓的连通图:
若无向图G是平凡图或者G中任意两点都是连通的,则称G是连通图,否则称G是非连通图。
关于弱连通图和强连通图:
弱连通图的概念是:如果略去D中各有向边的方向后所得无向图是连通图,则称D是弱连通图。
反之 若D中任何一对顶点都是互相可达的,则称D是强连通图。
所以这个问题完全可以转化策略为:
第一步: 首先我们不管它三七二十几,先进行连通性的判断。
第二步:
(1)如果是连通的,我们来判断此图的度的奇点的个数是0或者是2 ,如果是,则说明这个是欧拉图,即可以一笔画出,反之则不能一笔画出
(2)如果是非连通的,这说明这个图很定不能一笔画出。
代码为:
采用dfs算法求解:
1 /*nyoj 42 coder Gxjun*/
2 /*一笔画问题*/
3 #include<stdio.h>
4 #include<string.h>
5 #include<stdlib.h>
6 #define maxn 1005
7 int edge[maxn]; //度
8 bool vis[maxn],map[maxn][maxn];
9 int pp , qq ;
10 void dfs( int pos )
11 {
12 vis[pos]=true;
13 for( int i=1;i<=pp;i++)
14 if(!vis[i]&&map[pos][i])
15 dfs(i);
16 }
17
18 int main()
19 {
20 int test ,i,j;
21 int x,y;
22 bool flag;
23 //freopen("test.in","r",stdin);
24 scanf("%d",&test);
25 while(test--){
26 memset(edge,0,sizeof(edge));
27 memset(map,0,sizeof(map));
28 memset(vis,0,sizeof(vis));
29 scanf("%d%d",&pp,&qq);
30 for(i=0;i<qq;i++){
31 scanf("%d%d",&x,&y);
32 map[y][x]=map[x][y]=1;
33 edge[x]++;
34 edge[y]++;
35 }
36 dfs(1);
37 flag=true;
38 for(i=1;i<=pp ;i++){
39 if(!vis[i]){
40 flag=false;
41 break;
42 }
43 }
44 if(flag)
45 {
46 int ans=0;
47 for(i=1;i<=pp;i++)
48 if(edge[i]&1) ans++;
49 if( ans==0||ans==2 )
50 puts("Yes");
51 else
52 puts("No");
53 }
54 else
55 puts("No");
56 }
57 return 0;
58 }
采用并查集求解
代码:
1 /*并查集 @coder Gxjun*/
2 /*一笔画问题*/
3 #include<stdio.h>
4 #include<string.h>
5 #include<stdlib.h>
6 #define maxn 1001
7 int rank[maxn],father[maxn];
8 int edge[maxn];
9 int pp,qq;
10 void init(){
11 for(int i=1;i<=pp;i++){
12 father[i]=i;
13 rank[i]=1;
14 }
15 }
16 int set_find(int a){
17
18 while(a!=father[a])
19 a=father[a];
20 return a;
21 }
22 //带状态压缩的并查集
23 void set_union(int x,int y){
24 int a = set_find(x);
25 int b = set_find(y);
26 if(a!=b){
27 if(rank[a]>rank[b]){
28 father[b]=father[a];
29 rank[a]+=rank[b];
30 }
31 else{
32 father[a]=father[b];
33 rank[b]+=rank[a];
34 }
35 }
36 }
37
38 int main()
39 {
40 int test,i,j,x,y;
41 //freopen("test.in","r",stdin);
42 scanf("%d",&test);
43 while(test--){
44 scanf("%d%d",&pp,&qq);
45 memset(edge,0,sizeof(edge));
46 init();
47 for(i=0;i<qq;i++){
48 scanf("%d%d",&x,&y);
49 set_union(x,y);
50 ++edge[x];
51 ++edge[y];
52 }
53 for(i=1;i<=pp;i++)
54 if(rank[i]==pp) break;
55 if(i<=pp)
56 {
57 int ans=0;
58 for(j=1;j<=pp;j++)
59 if(edge[j]&1)ans++;
60 if(ans==0||ans==2) puts("Yes");
61 else puts("No");
62 }
63 else puts("No");
64 }
65 return 0;
66 }