Complete Tripartite CodeForces - 1228D（三分图染色）

You have a simple undirected graph consisting of nn vertices and mm 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 v1v1 and v2v2 be two some nonempty subsets of vertices that do not intersect. Let f(v1,v2)f(v1,v2) be true if and only if all the conditions are satisfied:

There are no edges with both endpoints in vertex set v1v1.
There are no edges with both endpoints in vertex set v2v2.
For every two vertices xx and yy such that xx is in v1v1 and yy is in v2v2, there is an edge between xx and yy.
Create three vertex sets (v1v1, v2v2, v3v3) 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(v1,v2), f(v2,v3)f(v2,v3), f(v3,v1)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 nn and mm (3≤n≤1053≤n≤105, 0≤m≤min(3⋅105,n(n−1)2)0≤m≤min(3⋅105,n(n−1)2)) — the number of vertices and edges in the graph.

The ii-th of the next mm lines contains two integers aiai and bibi (1≤ai<bi≤n1≤ai<bi≤n) — it means there is an edge between aiai and bibi. 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 nn integers. ii-th integer means the vertex set number (from 11 to 33) of ii-th vertex. Otherwise, print −1−1.

If there are multiple answers, print any.

Examples
Input
6 11
1 2
1 3
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
Output
1 2 2 3 3 3
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
-1
Note
In the first example, if v1={1}v1={1}, v2={2,3}v2={2,3}, and v3={4,5,6}v3={4,5,6} then vertex sets will satisfy all conditions. But you can assign vertices to vertex sets in a different way; Other answers like “2 3 3 1 1 1” will be accepted as well.

In the second example, it’s impossible to make such vertex sets.
题意：给你一张图，能否将这张图三分，就是三分图染色。将图中的点分成三份，三个集合中的点，一个集合中的点之间没有边相连，但是和其他两个集合中的点都有相连。
思路：由于这个图不一定是连通图。对于每个连通块来说，我们找到一个点染成1，与他相连的点都染成2。然后找到一个染成2的点，与他相连的点如果没有染色就染成1。如果染成2，就将它染色成3。
不是三分图的特征：
①每个连通块中三种颜色中有一个颜色没有。
②每个连通块中每个点链接的点数量等于这个联通块中其他两个颜色的数量。
③每条边链接的点染色不一样。
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxx=2e5+100;
const int maxn=3e5+100;
struct edge{
int to,next;
}e[maxn<<1];
int head[maxn<<1];
int vis[maxx];
int cor[maxx];
int sze[maxx];
int vis1[maxx];
vector<int> p[maxx];
int n,m,tot;
/*----------事前准备----------*/
inline void init()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(vis1,0,sizeof(vis1));
tot=0;
}
inline void add(int u,int v)
{
e[tot].to=v,e[tot].next=head[u],head[u]=tot++;
}
/*-------------dfs-------------*/
inline void dfs(int u,int &sum1,int &sum2,int &sum3,int &flag)//统计三个颜色的数量，一条边两边的点的颜色
{
sze[u]=0;
if(!flag) return ;
if(cor[u]==1) sum1++;
else if(cor[u]==2) sum2++;
else if(cor[u]==3) sum3++;
vis[u]=1;
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;sze[u]++;
if(cor[u]==cor[to])
{
flag=0;
return ;
}
if(vis[to]==0) dfs(to,sum1,sum2,sum3,flag);
}
}
inline void dfs1(int u,int sum1,int sum2,int sum3,int &flag)//一个点链接的点的数量是否等于其他两种颜色的数量
{
if(cor[u]==1)
{
if(sze[u]!=sum2+sum3)
{
flag=0;
return ;
}
}
if(cor[u]==2)
{
if(sze[u]!=sum1+sum3)
{
flag=0;
return ;
}
}
if(cor[u]==3)
{
if(sze[u]!=sum2+sum1)
{
flag=0;
return ;
}
}
vis1[u]=1;
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(vis1[to]==0) dfs1(to,sum1,sum2,sum3,flag);
}
}
int main()
{
int x,y;init();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
int j;
for(int k=1;k<=n;k++)
{
if(cor[k]==0)
{
j=k;
cor[k]=1;
for(int i=head[k];i!=-1;i=e[i].next)
{
int to=e[i].to;
j=to;
cor[to]=2;
}
for(int i=head[j];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(cor[to]==0) cor[to]=1;
else if(cor[to]==2) cor[to]=3;
}
}
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
vis[i]=1;
int flag=1;
int sum1=0,sum2=0,sum3=0;
dfs(i,sum1,sum2,sum3,flag);
if(flag==0||sum1==0||sum2==0||sum3==0)
{
puts("-1");
return 0;
}
else
{
dfs1(i,sum1,sum2,sum3,flag);
if(flag==0)
{
puts("-1");
return 0;
}
}
}
}
for(int i=1;i<=n;i++) cout<<cor[i]<<" ";cout<<endl;
}

努力加油a啊，(^o)/~

最后

以上就是高兴小蝴蝶为你收集整理的Complete Tripartite CodeForces - 1228D（三分图染色）的全部内容，希望文章能够帮你解决Complete Tripartite CodeForces - 1228D（三分图染色）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。