http://acm.timus.ru/problem.aspx?space=1&num=1040
刚开始 " If there are several flights that depart from one airport then the greatest
common divisor of their flight numbers should be equal to 1" 这句话理解错了呀 意思应该是
从某个机场出发的所有航班的编号最大公约数为1 唉 英语是硬伤呀
这个题需要用的到的一点是 gcd(x,x+1)==1 又由于原图是一个联通图(虽然题目中没有说)所有一遍dfs就可以
关键的地方是 除了第一个点 其他点如果多条边 至少有两条是编号相邻的 至于第一个点的话 由于有一个编号为 1 的边 所有没有关系
数组开小了 一直wa 你怎么不给我个 re 呀 无语了
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<map> #include<vector> #include<stack> #include<set> #include<map> #include<queue> #include<algorithm> #include<cmath> #define LL long long #define sint short int //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const int N=105; const double ex=1e-6; const int INF=0x3f3f3f3f; int head[N],I; struct node { int j,next; int k; }edge[N*N]; bool visited[N]; int num[N*N]; int T; void add(int i,int j,int k) { edge[I].j=j; edge[I].k=k; edge[I].next=head[i]; head[i]=I++; } void dfs(int x) { visited[x]=true; for(int t=head[x];t!=-1;t=edge[t].next) { if(num[edge[t].k]==0) num[edge[t].k]=T++; int j=edge[t].j; if(!visited[j]) { //num[edge[t].k]=T++; dfs(j); } } } int main() { //freopen("data.in","r",stdin); int n,m; while(cin>>n>>m) { memset(head,-1,sizeof(head)); I=0; for(int i=1;i<=m;++i) { int l,r; cin>>l>>r; add(l,r,i); add(r,l,i); } memset(visited,false,sizeof(visited)); T=1; memset(num,0,sizeof(num)); dfs(1); cout<<"YES"<<endl; for(int i=1;i<=m;++i) { cout<<num[i]<<" "; } cout<<endl; } return 0; }