You are given a directed graph with ??n vertices and ??m directed edges without self-loops or multiple edges.
Let‘s denote the ??k-coloring of a digraph as following: you color each edge in one of ??k colors. The ??k-coloring is good if and only if there no cycle formed by edges of same color.
Find a good ??k-coloring of given digraph with minimum possible ??k.
The first line contains two integers ??n and ??m (2≤??≤50002≤n≤5000, 1≤??≤50001≤m≤5000) — the number of vertices and edges in the digraph, respectively.
Next ??m lines contain description of edges — one per line. Each edge is a pair of integers ??u and ??v (1≤??,??≤??1≤u,v≤n, ??≠??u≠v) — there is directed edge from ??u to ??v in the graph.
It is guaranteed that each ordered pair (??,??)(u,v) appears in the list of edges at most once.
In the first line print single integer ??k — the number of used colors in a good ??k-coloring of given graph.
In the second line print ??m integers ??1,??2,…,????c1,c2,…,cm (1≤????≤??1≤ci≤k), where ????ci is a color of the ??i-th edge (in order as they are given in the input).
If there are multiple answers print any of them (you still have to minimize ??k).
4 5 1 2 1 3 3 4 2 4 1 4
1 1 1 1 1 1
3 3 1 2 2 3 3 1
2 1 1 2
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=100010; vector<int>G[maxn]; int flag; int u[maxn],v[maxn],vis[maxn]; void DFS(int u) { if(flag)return ; vis[u]=1;//正在访问 for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(vis[v]==0)DFS(v);//没访问过 else if(vis[v]==1){//下一个节点正在访问,即有环 flag=1; return ; } } vis[u]=2;//访问结束 } int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>u[i]>>v[i]; G[u[i]].push_back(v[i]); } for(int i=1;i<=n;i++){ if(!vis[i]){ DFS(i); } } if(!flag){ cout<<1<<endl; for(int i=1;i<=m;i++)cout<<1<<" "; cout<<endl; } else{ cout<<2<<endl; for(int i=1;i<=m;i++){ if(u[i]<v[i])cout<<1<<" "; else cout<<2<<" "; } cout<<endl; } return 0; }
原文：https://www.cnblogs.com/cherish-lin/p/11478332.html