CodeForces1228D - Complete Tripartite

传送门：CodeForces - 1228D

题目描述

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 $v_1$ and $v_2$ be two some nonempty subsets of vertices that do not intersect. Let $f(v_1,v_2)$ be true if and only if all the conditions are satisfied:

• There are no edges with both endpoints in vertex set $v_1$.
• There are no edges with both endpoints in vertex set $v_2$.
• For every two vertices $x$ and $y$ such that $x$ is in $v_1$ and $y$ is in $v_2$, there is an edge between $x$ and $y$.

Create three vertex sets $(v_1, v_2, v_3)$ which satisfy the conditions below;

• All vertex sets should not be empty.
• Each vertex should be assigned to only one vertex set.
• $f(v_1,v_2)$, $f(v_2,v_3)$, $f(v_3,v_1)$ are all true.

Is it possible to create such three vertex sets? If it’s possible, print matching vertex set for each vertex.

输入描述

The first line contains two integers n and m $(3≤n≤10^5, 0≤m≤min(3⋅10^5,\frac{n(n-1)}{2}))$ — the number of vertices and edges in the graph.

The i-th of the next m lines contains two integers $a_i$ and $b_i$ $(1≤a_i<b_i≤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.

输出描述

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.

思路分析

n个点m条边的无向图，问能不能将这些点分成三个集合，每个集合中的点互不相连，每个集合中的点除了自身集合的点之外，与其余每个点都相连。
我们只要确定一个点，就能确定哪些点跟它不在一个集合（与这个点相连的点），一开始都在一个集合，枚举每个点$u$，如果与之连边的点$v$的集合是同一个，那个使$v$这个点的集合+1。
如果集合数超出了3，那么肯定不行。
还有一点，三个集合之间的边数肯定等于互相之间点的乘积，最后判断总和等不等与$m$。

样例输入

6 11
1 2
1 3
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

样例输出

1 2 2 3 3 3

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#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;

const int INF = 0x3f3f3f3f;
const int N=3e5+50;

int color[N],ans[N];
vector<int>e[N];


int main() {
    int n,m;
    cin>>n>>m;
    for(int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        e[a].pb(b);
        e[b].pb(a);
    }
    for(int i=1; i<=n; i++)
        color[i]=1;
    int tot=1;
    for(int u=1; u<=n; u++) {
        for(auto v:e[u]) {
            if(color[v]==color[u])
                color[v]++;
            tot=max(tot,color[v]);
        }
    }

    if(tot!=3) {
        puts("-1");
    } else {
        for(int i=1; i<=n; i++)
            ans[color[i]]++;
        if(ans[1]*ans[2]+ans[2]*ans[3]+ans[1]*ans[3]!=m)
            puts("-1");
        else
            for(int i=1; i<=n; i++)
                cout<<color[i]<<" ";
    }
    
    return 0;
}