CodeForces-1217D Coloring Edges （有向图判环）

传送门：CodeForces-1217D

思路分析

如果没有环答案肯定是1
如果有环答案一定是2
因为有向图的环中，肯定存在由大指向小和由小指向大两种边
所以只需要将这两种边染不同色就行了

样例输入

3 3
1 2
2 3
3 1

样例输出

2
1 1 2

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

int a[N],b[N],in[N],n,m;
vector<int>e[N];

bool tp() {
    int cnt=0;
    queue<int>q;
    for(int i=1; i<=n; i++) if(in[i]==0) q.push(i);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        cnt++;
        for(auto v:e[u]) {
            in[v]--;
            if(in[v]==0) q.push(v);
        }
    }
    if(cnt!=n) return true;
    else return false;
}


int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>a[i]>>b[i];
        e[a[i]].push_back(b[i]);
        in[b[i]]++;
    }
    if(tp()) {
        cout<<2<<endl;
        for(int i=1; i<=m; i++) cout<<(a[i]>b[i]?1:2)<<" ";
    } else {
        cout<<1<<endl;
        for(int i=1; i<=m; i++) cout<<1<<" ";
    }



    return 0;
}