codeforces 1228D Complete Tripartite(图论+思维)

#include <bits/stdc++.h>
#define mp make_pair
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
typedef long long LL;
const int maxn = 3e5 + 10;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
int n, m, u, v, col[maxn], f[maxn], sz[maxn];
int find(int x) {
    return f[x] == -1 ? x : f[x] = find(f[x]);
}
vector<int> g[maxn];
vector<int> s[maxn][3];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for (int i = 1; i <= n; ++i)
        f[i] = -1;
    for (int i = 1; i <= n; ++i) {
        if (col[i] == 0) {
            col[i] = 1;
            int fu = find(i);
            if (g[i].empty()) {
                cout << -1;
                exit(0);
            }
            int to = g[i][0];
            for (int j = 0; j < g[i].size(); ++j) {
                int _to = g[i][j];
                int fv = find(_to);
                if (fv != fu)
                    f[fv] = fu;
                col[_to] = 2;
            }
            for (int j = 0; j < g[to].size(); ++j) {
                int _to = g[to][j];
                if (_to == i)
                    continue;
                int fv = find(_to);
                if (fv != fu)
                    f[fv] = fu;
                if (col[_to] == 0)
                    col[_to] = 1;
                else if (col[_to] == 2)
                    col[_to] = 3;
                else {
                    cout << -1;
                    exit(0);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        v = find(i);
        s[v][col[i] - 1].pb(i);
    }
    for (int i = 1; i <= n; ++i)
        if (!s[i][0].empty() || !s[i][1].empty() || !s[i][2].empty()) {
            if (s[i][0].empty() || s[i][1].empty() || s[i][2].empty()) {
                cout << -1;
                exit(0);
            }
        }
    for (int i = 1; i <= n; ++i) {
        v = find(i);
        if (col[i] == 1) {
            if (s[v][1].size() + s[v][2].size() != g[i].size()) {
                cout << -1;
                exit(0);
            }
        }
        else if (col[i] == 2) {
            if (s[v][0].size() + s[v][2].size() != g[i].size()) {
                cout << -1;
                exit(0);
            }
        }
        else if (col[i] == 3) {
            if (s[v][0].size() + s[v][1].size() != g[i].size()) {
                cout << -1;
                exit(0);
            }
        }
        for (int j = 0; j < g[i].size(); ++j) {
            int to = g[i][j];
            if (col[to] == col[i]) {
                cout << -1;
                exit(0);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << col[i] << " ";
}