一个无向简单图，问是否能把图分成三个点集，使得每个点集内部的点没有边相连，点集之间所有点都要两两相连。 好像3-sat啊 由于如果存在的话，那么一个点和它相连的点都不在同一个点集中。所以先假设存在，把点染成1、2、3三种颜色之一，然后判断是否成立即可。 必须有三种颜色 同一个点集中不能有边 点集A和点集B之间的边的个数必须要是size(A) * size(B)
#include<bits/stdc++.h> using namespace std; #define f first #define s second typedef long long LL; typedef pair<int,int> PII; typedef pair<LL,LL> PLL; const int N = 1e5 + 10; const int M = 3e5 + 10; int n,m,a,b,bel[N],vis[N],cnt[3]; PII s[M]; set<int> g[N]; vector<int> vec[3]; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); cin>>n>>m; memset(bel,-1,sizeof(bel)); for(int i = 0 ;i < m ;i ++){ cin>>a>>b; s[i].f = a;s[i].s = b; g[a].insert(b); g[b].insert(a); } for(int i = 0; i < 3; i ++) { memset(vis,0,sizeof(vis)); for(int j = 1;j <= n; j ++){ if(bel[j] == -1) { for(auto u : g[j]) vis[u] = 1; break; } } for(int j = 1; j <= n; j ++) if(!vis[j]){ if(bel[j] != -1) { cout<<-1<<endl; return 0; } bel[j] = i; vec[i].push_back(j); } } int st = 0 ; for(int i = 1; i <= n ;i ++) { if(bel[i] == -1) { cout<<-1<<endl; return 0; } st |= (1 << bel[i]); } int flag = 1; for(int i = 0 ;i < m; i ++){ int m1 = bel[s[i].f],m2 = bel[s[i].s]; if(m1 == m2) { flag = 0; break; } int stt = 0; stt |= (1<<m1) ; stt |= (1<<m2); if(stt == 3) cnt[0]++; else if(stt == 6) cnt[1]++; else if(stt == 5) cnt[2]++; } if(!flag || st != 7 || cnt[0] != (int)vec[0].size() * (int)vec[1].size() || cnt[1] != (int)vec[2].size() * (int)vec[1].size() || cnt[2] != (int)vec[2].size() * (int)vec[0].size()) cout<<-1<<endl; else { for(int i = 1 ; i <= n; i ++) { cout<<bel[i] + 1 <<' '; } cout<<endl; } return 0; }