题目链接：https://vjudge.net/contest/330119#problem/A
题目大意：
1.给出一张有向图，给该图涂色，要求同一个环里的边不可以全部都为同一种颜色。问最少需要多少颜色，并输出各边的涂色。
解题思路：
1.多画几张图就发现，颜色种类只会是1或者2。当不存在环的时候，全部涂1。当存在环的时候，环中可以分成两种边（小节点指向大节点涂1，大节点指向小节点涂2），就会发现所有的环颜色一定不会全部相同。
2.思考过1就发现这道题只需要判断是否存在环即可。可以用拓扑判断。原理为：在拓扑的过程中，入度为0的点会入队，但由于环上各点入度不可能为0.因此无法入队。所以在拓扑结束后，还存在没有入队的点，即存在环。
#include<stdio.h>
#include<string.h>
#include<queue>
#define mem(a, b) memset(a, b, sizeof(a))
const int MAXN = ;
const int MAXM = ;
using namespace std; int n, m;
int head[MAXN], cnt, in[MAXN], out[MAXN], tot;
queue<int> Q; struct Edge
{
int from, to, next;
}edge[MAXM]; void add(int a, int b)
{
cnt ++;
edge[cnt].from = a;
edge[cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt;
} int topo()
{
for(int i = ; i <= n; i ++)
{
if(!in[i])
{
Q.push(i);
tot ++;
}
}
while(!Q.empty())
{
int temp = Q.front();
Q.pop();
for(int i = head[temp]; i != -; i = edge[i].next)
{
int to = edge[i].to;
in[to] --;
if(!in[to])
{
Q.push(to);
tot ++;
}
}
}
if(tot != n) //存在 点 没有入队
return ;
else
return ;
} int main()
{
scanf("%d%d", &n, &m);
mem(head, -);
for(int i = ; i <= m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
in[b] ++, out[a] ++;
add(a, b);
}
if(topo()) //判是否有环存在
{
printf("2\n");
int flag = ;
for(int i = ; i <= cnt; i ++)
{
int a = edge[i].from, b = edge[i].to;
if(flag)
{
if(a < b)
printf("");
else
printf("");
flag = ;
}
else
{
if(a < b)
printf("");
else
printf("");
}
}
printf("\n");
}
else
{
printf("1\n1");
for(int i = ; i < m; i ++)
printf("");
printf("\n");
}
return ;
}