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}