https://www.luogu.com.cn/problem/P4782

看这篇讲解吧
https://www.luogu.com.cn/problem/solution/P4782

code:

#include<bits/stdc++.h>
#define N 2000050
using namespace std;
struct edge {
    int v, nxt;
} e[N << 2];
int p[N], eid;
void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}
void insert(int u, int v) { //printf("%d --> %d\n", u, v);
    e[eid].v = v;
    e[eid].nxt = p[u];
    p[u] = eid ++;
}
int dfn[N], low[N], tot, n, m, top, sta[N], col[N], sz, in[N];
void dfs(int u) {
    low[u] = dfn[u] = ++ tot;
    sta[++ top] = u, in[u] = 1;
    for(int i = p[u]; i + 1; i = e[i].nxt) {
        int v = e[i].v;
        if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
        else if(in[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        ++ sz;
        while(sta[top] != u) {
            col[sta[top]] = sz;
            in[sta[top]] = 0; top --;
        }
        col[sta[top]] = sz;
        in[sta[top]] = 0; top --;
    }
}
int main() {
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        int u, v, a, b;
        scanf("%d%d%d%d", &u, &a, &v, &b);
        if(a && b) insert(u + n, v), insert(v + n, u);
        if(a && !b) insert(u + n, v + n), insert(v, u);
        if(!a && b) insert(u, v), insert(v + n, u + n);
        if(!a && !b) insert(u, v + n), insert(v, u + n);
    }
    for(int i = 1; i <= n + n; i ++) if(!dfn[i]) dfs(i);
    for(int i = 1; i <= n; i ++) {
        if(col[i] == col[i + n]) {
            printf("IMPOSSIBLE");
            return 0;
        }
    }
    printf("POSSIBLE\n");
    for(int i = 1; i <= n; i ++) printf("%d ", col[i] < col[i + n]);
    return 0;
}