codeforces 687 A. NP-Hard Problem(交叉染色法)

题目链接

题意:找两个不相交点集使得对于每一条边至少有一个顶点在点集中

思路:判断能否构成二分图。染色即可。

需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333.

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年09月03日 星期六 01时04分40秒
  4File Name :code/hdu/687A.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <deque>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <bitset>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27using namespace std;
 28const double eps = 1E-8;
 29const int dx4[4]={1,0,0,-1};
 30const int dy4[4]={0,-1,1,0};
 31const int inf = 0x3f3f3f3f;
 32const int N=1E5+7;
 33const int M=2E5+7;
 34int n,m;
 35struct Edge
 36{
 37    int v;
 38    int nxt;
 39}edge[M];
 40int cnt = 0 ;
 41int head[N];
 42int col[N];
 43void addedge( int u,int v)
 44{
 45    edge[cnt].v = v;
 46    edge[cnt].nxt = head[u];
 47    head[u] = cnt;
 48    cnt++;
 49}
 50bool dfs( int u,int x,int fa)
 51{
 52    col[u] = x;
 53    for ( int i = head[u] ;  i!=-1 ; i = edge[i].nxt)
 54    {
 55	int v  = edge[i].v;
 56	if (v==fa) continue;
 57	if (col[v]==1-x) continue;
 58	if (col[v]==x) return false;
 59	if (!dfs(v,1-x,u)) return false;
 60    }
 61    return true;
 62}
 63bool solve()
 64{
 65    for ( int i = 1  ; i <= n ; i++) if (col[i]==-1) if (!dfs(i,0,-1)) return false;
 66    return true;
 67}
 68int main()
 69{
 70	#ifndef  ONLINE_JUDGE 
 71	freopen("code/in.txt","r",stdin);
 72  #endif
 73	cin>>n>>m;
 74	ms(col,-1);
 75	ms(head,-1);
 76	for ( int i = 1 ; i <= m ; i++)
 77	{
 78	    int u,v;
 79	    cin>>u>>v;
 80	    addedge(u,v);
 81	    addedge(v,u);
 82	}
 83	if (!solve())
 84	    puts("-1");
 85	else 
 86	{
 87	    vector<int>ans1,ans2;
 88	    for ( int i = 1 ; i <= n ; i++)
 89	    {
 90		if (col[i]==-1) continue;
 91		if ( col[i]==0) ans1.push_back(i);
 92		else ans2.push_back(i);
 93	    }
 94	    int siz1 = ans1.size();
 95	    int siz2 = ans2.size();
 96	    cout<<siz1<<endl;
 97	    for ( int i = 0 ; i < siz1 ; i++) cout<<ans1[i]<<" ";
 98	    cout<<endl;
 99	    cout<<siz2<<endl;
100	    for  ( int i = 0 ; i < siz2 ; i++) cout<<ans2[i]<<" ";
101	    cout<<endl;
102	}
103  #ifndef ONLINE_JUDGE  
104  fclose(stdin);
105  #endif
106    return 0;
107}