Complete Tripartite

Created by LXC on Fri Jun 7 22:59:43 2024

https://codeforces.com/problemset/problem/1228/D

ranting: 1900

tag: brute force, constructive algorithms, graphs, hashing, implementation

problem

有一个 $n$ 个点 $m$ 条边的无向图，每一对顶点中最多有一条边。

设 $v_1,v_2$ 是两个不相交的非空子集，当满足下列条件时，$f(v_1,v_2)$ 的值为真：

• $v_1$ 中的点之间不存在边。

• $v_2$ 中的点之间不存在边。

• 对于 $\forall x\in v_1$，$\forall y\in v_2$，$x$ 和 $y$ 之间有边。

问是否存在三个点集 $v_1,v_2,v_3$，使得 $f(v_1,v_2)$，$f(v_2,v_3)$ 和 $f(v_1,v_3)$ 的值均为真。

如果是，输出每一个点所在的点集；否则输出 -1。

solution

一个set集合，通过遍历每个元素x，然后将x所连接的点y在set中移除，如果y在set中的话。这样得到的集合内部元素各点之间必定不存在边。

我们将上一个集合中移除的点再次执行此算法，又可以得到一个互不存在边的点集。

再将上一个集合移除的点形成第三个集合，需要判断是否形成互不存在边的点集。

我们得到三个点集，接下来需要判断每个集合中的点与其他集合中的点存在边。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t> ostream& operator<<(ostream& os,const set<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m;
    cin >> n >> m;
    vector g(n+1, vector<int>());
    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    set<int> st1, st2, st3;
    for (int i=1; i<=n; i++) st1.insert(i);
    for (int i=1; i<=n; i++) {
        if (st1.count(i))
        for (int j:g[i]) {
            if (st1.count(j)) st2.insert(j), st1.erase(j);
        }
    }
    for (int i=1; i<=n; i++) {
        if (st2.count(i))
        for (int j:g[i]) {
            if (st2.count(j)) st3.insert(j), st2.erase(j);
        }
    }
    for (int i:st3) {
        for (int j:g[i]) {
            if (st3.count(j)) {
                cout << "-1\n";
                return ;
            }
        }
    }
    if (st2.empty() || st3.empty()) {
        cout << "-1\n";
        return ;
    }
    int sz1 = st1.size(), sz2 = st2.size(), sz3 = st3.size();
    for (int i:st1) {
        if (g[i].size() != sz2+sz3) {
            cout << "-1\n";
            return ;
        }
    }
    for (int i:st2) {
        if (g[i].size() != sz1+sz3) {
            cout << "-1\n";
            return ;
        }
    }
    for (int i:st3) {
        if (g[i].size() != sz2+sz1) {
            cout << "-1\n";
            return ;
        }
    }
    // cout << st1 << endl;
    // cout << st2 << endl;
    // cout << st3 << endl;
    
    vector<int> v(n+1);
    iota(v.begin(), v.end(), 0);
    for (int i:st1) v[i] = 1;
    for (int i:st2) v[i] = 2;
    for (int i:st3) v[i] = 3;
    for (int i=1; i<=n; i++) {
        cout << v[i] << " ";
    }
    cout << "\n";

}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}