codeforces - 1217D Coloring Edges

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.

Input
The first line contains two integers n and m (2≤n≤5000, 1≤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≤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.

Output
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 c1,c2,…,cm (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).

Examples
inputCopy
4 5
1 2
1 3
3 4
2 4
1 4
outputCopy
1
1 1 1 1 1
inputCopy
3 3
1 2
2 3
3 1
outputCopy
2
1 1 2

根据贪心，我们可以知道我们每次尽量使用只吃一个食物，这样必然正确。

所以我们就需要怎么去保证每次只吃一个。

于是我们可以使用并查集，将食物与食物之间连起来，如果当前这条链的长度为n，可以得出能够满足的人为 n-1 ，所以如果当前的人的食物都被连起来了，那么这个人必然会贡献一点答案，否则将食物之间连起来。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int f[N],n,k,res;
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)	f[i]=i;
	for(int i=1;i<=k;i++){
		int a,b;	cin>>a>>b;	int fa=find(a);	int fb=find(b);
		if(fa==fb)	res++;
		else	f[fa]=fb;	
	}
	cout<<res<<endl;
	return 0;
}