题目链接：https://www.luogu.org/problem/CF1217D
题意：请给一个有向图着色，使得没有一个环只有一个颜色，您需要最小化使用颜色的数量。
分析：无环的时候显然答案就是1
而有环答案是2
证明： 首先我们可以考虑dfs树，在有向图中，只存在三种边，返祖边，树边，横叉边， 然而横叉边在有向图中并不能构成一个环，所以在有向图中，一个环必然同时包含返祖边和树边两种边，那么我们只需要将所有的返祖边染成1，树边染成2，那么一个换中就肯定不止一种颜色了。
相关知识：图的遍历中，往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义
vis = 0,表示该顶点没没有被访问
vis = 1,表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回
vis = 2,，表示该顶点已经被访问，其子孙后代也已经访问完，也已经从该顶点返回，注意没返回是不算的，这里可以假设这个定点还有个null孩子，还没访问这个null孩子就不算已经访问完
DFS过程中，对于一条边u->v
vis[v] = 0,说明v还没被访问，v是首次被发现，u->v是一条树边，真正的dfs路径中的边
vis[v] = 1,说明v已经被访问，但其子孙后代还没有被访问完（正在访问中），而u又指向v？说明u就是v的子孙后代，u->v是一条后向边，因此后向边又称返祖边，有环的时候回去的边，因此判断有没有环可以判断有没有后向边就可以了。
vis[v] = 3,z说明v已经被访问，其子孙后代也已经全部访问完，u->v这条边可能是一条横叉边，或者前向边，比如跨树的时候其实就是横叉变，就是一棵树访问完了访问下一棵树了该。而前向边可以理解为就是父亲指向孩子，但是已经访问过了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5010; const int N=1e3+7; const int inf=0x3f3f3f3f; int head[maxn]; int nxt[maxn]; int to[maxn]; int vis[maxn]; int cnt; int ans[maxn]; bool cyc; void add(int u,int v){ cnt++; to[cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; } void dfs(int u){ vis[u]=1;//点u已经被访问了但其子孙后代还没被访问完。 for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(vis[v]==0){//这是条树边 dfs(v); ans[i]=1; } else if(vis[v]==2)//横断边 ans[i]=1; else if(vis[v]==1)//返祖边 cyc=1,ans[i]=2; } vis[u]=2;//点u已经被访问了 } int main(){ int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); add(u,v); } for(int i=1;i<=n;i++){ if(!vis[i]) dfs(i); } if(cyc)printf("2\n"); else printf("1\n"); for(int i=1;i<m;i++)printf("%d ",ans[i]); printf("%d\n",ans[m]); return 0; }