题目要求与每个顶点相连的所有边编号最大公约数为1，其实只要其中的两条边编号互质，所有边编号的最大公约数一定为1。我们知道相邻的数字一定互质，那么
只要与一个顶点相连的所有边中有两条编号相邻，这个顶点就可以符合条件。DFS序列，对边进行编号刚好可以构造出满足要求的解，并且无解的情况是不存在的。
1 #include <iostream>
2 using namespace std;
3 int n,m;
4 int con[60][60];
5 int link[60][60];
6 int num[5000];
7 int now;
8 bool v[60];
9 bool p[5000];
10
11 void dfs(int x){
12 for (int i=1;i<=con[x][0];++i) if (!p[link[x][i]]){
13 p[link[x][i]]=true;
14 num[link[x][i]]=++now;
15 if (!v[con[x][i]]){
16 v[con[x][i]]=true;
17 dfs(con[x][i]);
18 }
19 }
20 }
21
22 int main(){
23 scanf("%d %d",&n,&m);
24 for (int i=1;i<=m;++i){
25 int a,b;
26 scanf("%d %d",&a,&b);
27 con[a][++con[a][0]]=b;
28 con[b][++con[b][0]]=a;
29 link[a][++link[a][0]]=i;
30 link[b][++link[b][0]]=i;
31 }
32 v[1]=true;
33 dfs(1);
34 printf("YES\n");
35 for (int i=1;i<=m;++i) printf("%d ",num[i]);
36 }
37
posted on 2008-11-06 16:34
Joseph 阅读(175)
评论(0) 编辑 收藏 引用