CodeForces 687A NP-Hard Problem（二分图判定）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这本来一个挺简单的题呢，结果让我给想复杂了，二分图就是把图分成了两部分，然后不同颜色各一边，肯定是满足题目中说的边和点的条件的，真是犯二了。。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define N 100010
vector<int> vt[N];
int clo[N],n;
int out1[N],out2[N];
map<int,int>mp;
queue<int> que;
void Memset(int *a,int k)
{
for(int i = ; i <= n; i++) a[i] = k;
}
bool bfs(int x)
{
clo[x] = ;
while(!que.empty()) que.pop();
que.push(x);
int now,nxt,len;
while(!que.empty())
{
now = que.front();
que.pop();
len = vt[now].size();
for(int i = ; i < len; i++)
{
nxt = vt[now][i];
if(clo[nxt] == -)
{
clo[nxt] = clo[now]^;
que.push(nxt);
}
if(clo[nxt]==clo[now]) return false;
}
}
return true;
}
bool Judge()
{
Memset(clo,-);
for(int i = ; i <= n; i++)
{
if(clo[i]==- && bfs(i) == false) return false;
}
return true;
}
int main()
{
int m,a,b,tot;
cin>>n>>m;
for(int i = ; i <= n; i++)
{
vt[i].clear();
}
mp.clear();
for(int i = ; i < m; i++)
{
cin>>a>>b;
mp[a] = ;
mp[b] = ;
vt[a].push_back(b);
vt[b].push_back(a);
}
if(Judge() == false) printf("-1\n");
else
{
int tot1,tot2;
tot1 = tot2 = ;
for(int i = ; i <= n; i++)
{
if(mp[i] == )
{
if(clo[i] == ) out1[tot1++] = i;
if(clo[i] == ) out2[tot2++] = i;
}
}
cout<<tot1<<endl;
for(int i = ;i < tot1;i++){
if(i==tot1-) cout<<out1[i]<<endl;
else cout<<out1[i]<<" ";
}
cout<<tot2<<endl;
for(int i = ;i < tot2;i++){
if(i==tot2-) cout<<out2[i]<<endl;
else cout<<out2[i]<<" ";
}
}
return ;
}