随笔 - 32  文章 - 2  trackbacks - 0
<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8806
  • 排名 - 1247

最新评论

阅读排行榜

评论排行榜

题目要求与每个顶点相连的所有边编号最大公约数为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 阅读(176) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理