題意
https://vjudge.net/problem/CodeForces-1228D
有一個n個頂點m條邊的無向圖，在一對頂點中最多有一條邊，
設v1，v2是兩個不相交的非空子集，當滿足以下條件時f（v1，v2）為真
- v1中的點之間不存在邊
- v2中的點之間不存在邊
- 對于在v1v2中的每一對頂點，x在v1中，y在v2中，xy之間有邊
所有點集不為空，且不相交，是否有v1，v2，v3使得f（v1，v2）、f（v2，v3）、f（v3，v1）均為真
如果有輸出每個點所在的點集（1,2,3），否則輸出-1
思路
這題比賽沒敢開，其實就是個亂搞題，只不過細節很多，，
主要思路就是先隨便選一個點插入第一個集合，然后和這個點直接相連的點肯定不能插入第一個集合，不相連的點插入第一個集合，再在不在第一個集合的點中隨便選一個點，類似的擴展下去只不過要注意不能用集合1中的點，這樣第二個集合就構造好了，剩余的點插入第三個集合，最后判斷兩兩集合是否每個點都相連，這里用map<int,int> mp[N]判斷是否相連比較舒服~
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector<int> g[N];
unordered_map<int,int> mp[N];
int q[N];
int main()
{
std::ios::sync_with_stdio(false);
int n,m,flag=0;
cin>>n>>m;
for(int i=1; i<=m; i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
mp[u][v]=mp[v][u]=1;
}
if(m==0)
{
cout<<-1<<endl;
return 0;
}
set<int> a,b,c;
map<int,int> t;
a.insert(1);
int sz=g[1].size(),bb;
if(sz==0)
{
cout<<-1<<endl;
return 0;
}
for(int i=1; i<=n; i++)
{
if(!mp[1][i])
a.insert(i);
else
bb=i;
}
if(a.size()==n)
{
cout<<-1<<endl;
return 0;
}
sz=g[bb].size();
if(sz==0)
{
cout<<-1<<endl;
return 0;
}
b.insert(bb);
for(int i=1; i<=n; i++)
{
if(!mp[bb][i]&&a.find(i)==a.end())
{
b.insert(i);
}
}
for(int i=1; i<=n; i++)
{
if(a.find(i)==a.end()&&b.find(i)==b.end())
{
c.insert(i);
}
}
for(int i:a)
{
for(int j:b)
{
if(!mp[i][j])
{
flag=1;
break;
}
}
for(int j:c)
{
if(!mp[i][j])
{
flag=1;
break;
}
}
if(flag)
break;
}
for(int i:b)
{
for(int j:c)
{
if(!mp[i][j])
{
flag=1;
break;
}
}
}
if(a.size()+b.size()+c.size()!=n||
a.size()==0||b.size()==0||c.size()==0||a.size()*b.size()+a.size()*c.size()+b.size()*c.size()!=m)
flag=1;
if(flag)
{
cout<<-1<<endl;
}
else
{
for(int i:a)
q[i]=1;
for(int i:b)
q[i]=2;
for(int i:c)
q[i]=3;
for(int i=1; i<=n; i++)
cout<<q[i]<<" ";
cout<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127170.html
標籤：其他
下一篇：資料結構之鏈表-動圖演示