一个航空公司为Ural州立大学80周年校庆提供了赞助。作为报答，航空公司希望Ural大学能帮他们一个忙。此公司开放n个机场，这些机场之间有若干条航线。为了简化工作，这些航线从1到M依次标号。如果两个机场之间有一条航线，那么飞机可以从其中任意一个机场起飞到另一个机场。任意两个机场之间只有可能有一条直达航线。 航空公司知道它们的飞机有可能吸引恐怖分子， 为了给恐怖分子制造一些麻烦，公司决定给航线编号的时候遵循一些特别的规则。如果有几条航线和同一个机场相关联，那么这些航线编号的最大公约数必须等于1。航空公司求助于你。 (记住，此公司是赞助商，你必须完全正确的解决这个问题。
你的任务是写一个程序，找到符合要求的编号方法或确定不存在符合题意的编号方法。若存在多组编号方法，输出其中任意一个即可。
input：
输入的第一行包含两个用一个空格隔开的整数n和m (2 <= n <= 50)。 接下来的m 行包含了航线的信息。一条航线由它所连接的两个机场而唯一确定。机场编号之间用一个空格隔开。
output：
若存在一个可行的编号方法就在第一行输出'YES'，否则输出'NO'。 如果答案是'YES'，那么第二行应该输出一个可行的航线编号方案。编号顺序和航线在输入文件中出现的顺序一致。航线的编号之间用一个空格隔开。
input：
6 5
1 2
2 3
2 4
4 3
5 6
output：
YES
4 2 3 1 5
注意：其实测试数据中没有NO的情况，还有连不连通没有关系的，直接用dfs一直搜到m即可。
【参考程序】：
#include<iostream>
using namespace std;
int n,m,num;
bool use[51][51];
int f[51][51],cnt[51][51],h[1250];
void make(int now)
{
int k,t;
if (num==m) return ;
for (int i=1;i<=cnt[now][0];i++)
{
k=cnt[now][i];
if (!use[k][now])
{
use[k][now]=use[now][k]=true;
num++;
t=f[now][k];
h[t]=num;
make(k);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(cnt,0,sizeof(cnt));
memset(use,false,sizeof(use));
int a,b;
for (int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
f[a][b]=i;cnt[a][0]++;cnt[a][cnt[a][0]]=b;
f[b][a]=i;cnt[b][0]++;cnt[b][cnt[b][0]]=a;
}
num=0;
make(1);
printf("YES\n");
for (int i=1;i<=m-1;i++)
printf("%d ",h[i]);
printf("%d\n",h[m]);
return 0;
}
|