题目链接：http://codeforces.com/problemset/problem/687/A
题意：给出一个n个点m条边的图，分别将每条边连接的两个点放到两个集合中，输出两个集合中的点，若不可能则输出-1；
思路：通过画图我们不难发现，图中没有出现长度为奇数的环则是可行的，反之则是不行的．
对于这点我们可以直接用dfs搜索+染色，对于当前标记为1的点，我们将其所有儿子标记为2, 对于当前标记为2的点，将其所有儿子标记为1，若出现某个节点的标记与其儿子相同，则有长度为奇数的环。
代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int MAXN=1e5+10;
5 vector<int> v[MAXN];
6 vector<int> st1, st2;
7 bool flag=false;
8 int vis[MAXN];
9
10 void dfs(int point){
11 if(flag){
12 return;
13 }
14 for(int i=0; i<v[point].size(); i++){
15 int cnt=v[point][i];
16 if(vis[point]==vis[cnt]){
17 flag=true;
18 return;
19 }else if(!vis[cnt]){
20 if(vis[point]==1){
21 vis[cnt]=2;
22 st2.push_back(cnt);
23 dfs(cnt);
24 }else if(vis[point]==2){
25 vis[cnt]=1;
26 st1.push_back(cnt);
27 dfs(cnt);
28 }
29 }
30 }
31 }
32
33 int main(void){
34 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
35 int n, m, x, y;
36 cin >> n >> m;
37 while(m--){
38 cin >> x >> y;
39 v[x].push_back(y);
40 v[y].push_back(x);
41 }
42 for(int i=1; i<=n; i++){
43 if(v[i].size()==0){
44 continue;
45 }else if(!vis[i]){
46 vis[i]=1;
47 st1.push_back(i);
48 dfs(i);
49 }
50 }
51 if(flag){
52 cout << -1 << endl;
53 }else{
54 cout << st1.size() << endl;
55 for(int i=0; i<st1.size(); i++){
56 cout << st1[i] << " ";
57 }
58 cout << endl;
59 cout << st2.size() << endl;
60 for(int i=0; i<st2.size(); i++){
61 cout << st2[i] << " ";
62 }
63 cout << endl;
64 }
65 return 0;
66 }