「题解」Complete Tripartite

“完全”的三分图的存在性判定问题……

一 题目

Source

Descriptions

You have a simple undirected graph consisting of n vertices and m edges. The graph doesn’t contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Let’s make a definition.
Let v1 and v2 be two some nonempty subsets of vertices that do not intersect. Let f(v1,v2) be true if and only if all the conditions are satisfied:
There are no edges with both endpoints in vertex set v1.
There are no edges with both endpoints in vertex set v2.
For every two vertices x and y such that x is in v1 and y is in v2, there is an edge between x and y.

Create three vertex sets (v1, v2, v3) which satisfy the conditions below;
All vertex sets should not be empty.
Each vertex should be assigned to only one vertex set.
f(v1,v2), f(v2,v3), f(v3,v1) are all true.
Is it possible to create such three vertex sets? If it’s possible, print matching vertex set for each vertex.

Input

The first line contains two integers n and m (3≤n≤105, 0≤m≤min(3⋅105,n(n−1)2)) — the number of vertices and edges in the graph.
The i-th of the next m lines contains two integers ai and bi (1≤ai<bi≤n) — it means there is an edge between ai and bi. The graph doesn’t contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Output

If the answer exists, print n integers. i-th integer means the vertex set number (from 1 to 3) of i-th vertex. Otherwise, print −1.
If there are multiple answers, print any.

---

二 题解

就是给你一张图，让你判定能不能把这张图上找出三个互异点集，使它们的并是总点集，且有任意两点集中的点总有边相连。
实际上可以看成一个”完全“（任意两点间都有边相连）的三分图。

显然，若图不连通，则必定无解。

然后在保证图联通的情况下，对于一个可行的极大的点集，其中的每个点能到达的 所有点 组成的点集总是一样的。换句话说，能到达的点集相同的点总属于同一个可行的极大的点集。那么只需要把这些点拎出来就好了，最后形成的点集个数如果为 3 就表明恰好有解，再给每个点集编号就好了。

也可以推广到完全 k 分图的判定

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

const int CN = 5e5+5;

class edge{
  public: int id; vector<int> to; // to : 每个点能到达的点集
}E[CN];
class ufs{ // 判联通
  public: int fa[CN]; ufs() {for(int i=1;i<=300001;i++) fa[i] = i;}
    int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
    bool exm(int x,int y) {return find(x) != find(y);}
    void merge(int x,int y) {fa[find(x)] = find(y);} 
}S;

/* v define */
int n,m;
int bel[CN];

/*  */
bool CheCon(){ // 判联通
    for(int i=1;i<=n;i++) S.find(i);
    int R = S.fa[1];
    for(int i=2;i<=n;i++) if(S.fa[i] != R) return false;
    return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y; scanf("%d%d",&x,&y);
        E[x].to.push_back(y);
        E[y].to.push_back(x);
        if(S.exm(x, y)) S.merge(x,y);
    }

    if(CheCon()){
        for(int i=1;i<=n;i++)
            sort(E[i].to.begin(), E[i].to.end()); // 排序，方便下面判等
        for(int i=1;i<=n;i++){ // 相当于一个离散化的过程
            if(!bel[i]){
                bel[i] = ++bel[0];
                for(int j=1;j<=n;j++)
                    if(E[i].to == E[j].to) bel[j] = bel[0];
            }
        }
        if(bel[0] == 3){
            for(int i=1;i<=n;i++) printf("%d ",bel[i]);
        }
        else printf("-1");
    }
    else printf("-1");

    return 0;
}