D - Complete Tripartite
思路:這個題是個染色問題。了解題意就差不多寫出來一半了。開始的時候還想用離散化來儲存每個點的狀态,即它連接配接的點有哪些,但很無奈,點太多了,範圍内肯定存不完,于是想到用
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;
}