Educational Codeforces Round 72 (Rated for Div. 2)-D. Coloring Edges(思维、有向图鉴环)

题面链接
本题题意给你一个有向图，每个边着色，不能有同种颜色的边形成环，输出每条边的颜色(颜色用数字代替)，可以看到，只要图中形成了环，这个环就能用两种颜色着色来满足题意，所以只要小点向大点走用一种颜色，大点向小点走用一种颜色就可以，本题关键就是有向图鉴环的问题。
用邻接矩阵存图，走过的点标记为2，本路径中标记为1，没走过就是0，那么我们在dfs过程中，遇见了1就可以判定有环，就用两种颜色。
代码如下：

#include <iostream>
#include <cstring>
#include<cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <ctime>
#include <cstring>
#include <cmath>
#include <stack>
#include <set>

#define INF 0x3f3f3f3f
#define rep(i, n) for(ll i=0;i<n;i++)
#define per(i, n) for(int i=n;i>=0;i--)
#define rep2(i, n) for(ll i=1;i<=n;i++)
#define pb(x) push_back(x)
#define clint(x, n) memset(x,n,sizeof(x))
#define mp make_pair
#define fi first
#define se second
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define ull unsigned long long
#define ud long double
#define pii pair<int,int>
using namespace std;
const int maxn = 1e4;
const int inf = 1000000 + 10;
const int mod = 1e9 + 7;
const int MAX = 123123;
string str;
struct edge {
    int u, v, c;
} ed[5005];
int ma[5002][5002];
int vis[50002];
bool huan = 0;
ll b, g, n, t, x, m;
int dfs(int i)
{
    vis[i]=1;
    for(int j=1;j<=n;j++)
    {
        if(ma[i][j]) {
            if (vis[j] == 1) {
                huan = 1;
                continue;
            }
            if (vis[j] == 2)
                continue;
            dfs(j);
        }
    }
    vis[i]=2;
    return 0;
}
int main() {
    IO;
    cin >> n >> m;
    clint(ma, 0);
    clint(vis, 0);
    rep(i, m) {
        cin >> ed[i].u >> ed[i].v;
        ma[ed[i].u][ed[i].v]=1;
        if (ed[i].u < ed[i].v) ed[i].c = 1;
        else ed[i].c = 2;
    }
    rep2(i,n)
        if(vis[i]==0) dfs(i);
    if (huan) {
        cout<<2<<endl;
        rep(i, m) {
            if (i) cout << ' ';
            cout << ed[i].c;
        }
    } else {
        cout<<1<<endl;
        rep(i, m) {
            if (i) cout << ' ';
            cout << 1;
        }
    }
    cout << endl;
    return 0;
}