Coloring Edges(Codeforces-1217D)(有向图返祖边染色)

前言

可能以前会，但现在不会，但又会了

题目

思路

说白了就是找环后将返祖边颜色染为2
我们可以复习一下有向图DFS树边的类型，树边、返祖边、横叉边、后向边
怎么找环呢，我们并不能简单的vis，因为可能这样：

于是我们需要给每个点3个状态：未访问，正在访问它的子树，已访问。
当然我们可以用栈来维护此时访问的点，但也能用不同标记表示
我们1次DFS可能找不完点，要注意一下需要多次DFS，一定可以把访问到的环至少一条边找完

代码

#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 100000
#define INF 0x3f3f3f3f
struct Edge{
    int v,id,nxt;
}edge[2*MAXN+5];
int ecnt,head[MAXN+5];
inline void Addedge(int u,int v,int id){
    edge[++ecnt]=(Edge){
    v,id,head[u]},head[u]=ecnt;return ;
}
bool f;
int col[MAXN+5],vis[MAXN+5];
void DFS(int u){
    vis[u]=1;for(int i=head[u];i;i=edge[i].nxt){
    int v=edge[i].v,id=edge[i].id;col[id]=1;if(vis[v]){
    if(vis[v]==1)f=1,col[id]=2;continue;}DFS(v);}vis[u]=2;return ;
}
int main(){
    int n=read(),m=read();for(int i=1;i<=m;i++){
    int u=read(),v=read();Addedge(u,v,i);}for(int i=1;i<=n;i++)if(!vis[i])DFS(i);puts(f?"2":"1");for(int i=1;i<=m;i++)printf("%d",col[i]),putchar(i==m?'\n':' ');return 0;
}

后记

在网上发现了更好的做法，你跑一遍拓扑排序判环，如果没有环全输出1，否则一个环上一定存在 $u>v$ 的边和 $u<v$ 的边，不是环上的边可以不管（1,2颜色都可以）于是直接 $u>v$ 的边颜色为1, $u<v$ 的边颜色为2即可
妙啊！