思路:这个题是个染色问题。理解题意就差不多写出来一半了。开始的时候还想用离散化来储存每个点的状态,即它连接的点有哪些,但很无奈,点太多了,
long long
范围内肯定存不完,于是想到用python
来写,但是 py 也没有很熟练.....便放弃了。需要注意的:
要统计总共有多少颜色,不然会漏掉只有两种颜色的情况,这种情况是输出
-1
的。还有前向星存边的时候记得开两倍。
代码:
// Created by CAD on 2019/10/2.
#include <bits/stdc++.h>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;
const int maxn=3e5+5;
struct edge{
int to,next;
}e[maxn<<1];
int cnt,head[maxn],color[maxn],vis[maxn],n,m,blo;
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
bool check(int x)
{
if(++blo==4) return false;
color[x]=blo;
int num=0;
for(int i=head[x];i;i=e[i].next)
vis[e[i].to]=1,num++;
for(int i=1;i<=n;++i)
{
if(i==x||vis[i]) continue;
int cnt2=0;
color[i]=blo;
for(int j=head[i];j;j=e[j].next)
{
if(!vis[e[j].to]) return false;
cnt2++;
}
if(cnt2!=num) return false;
}
mst(vis,0);
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;++i)
cin>>u>>v,add(u,v),add(v,u);
for(int i=1;i<=n;++i)
if(!color[i])
if(!check(i)) return puts("-1");
if(blo!=3) return puts("-1");
for(int i=1;i<n;++i)
cout<<color[i]<<" ";
cout<<color[n]<<endl;
return 0;
}