C. NP-Hard Problem time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
Recently, Pari and Arya did some research about NP-Hard problems and they found theminimum vertex cover problem very interesting.
Suppose the graph G is given. Subset A of its vertices is called a vertex cover of this graph, if for each edgeuv there is at least one endpoint of it in this set, i.e.
or
(or both).
Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover.
They have agreed to give you their graph and you need to find two disjoint subsets of its vertices A andB, such that bothA andB are vertex cover or claim it's impossible. Each vertex should be given to no more than one of the friends (or you can even keep it for yourself).
Input
The first line of the input contains two integers n andm (2 ≤ n ≤ 100 000,1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively.
Each of the next m lines contains a pair of integersui andvi (1 ≤ ui, vi ≤ n), denoting an undirected edge betweenui andvi. It's guaranteed the graph won't contain any self-loops or multiple edges.
Output
If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes).
If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integerk denoting the number of vertices in that vertex cover, and the second line containsk integers — the indices of vertices. Note that because ofm ≥ 1, vertex cover cannot be empty.
Examples Input
4 2
1 2
2 3
Output
1
2
2
1 3
Input
3 3
1 2
2 3
1 3
Output
-1
Note
In the first sample, you can give the vertex number 2 to Arya and vertices numbered1 and3 to Pari and keep vertex number4 for yourself (or give it someone, if you wish).
In the second sample, there is no way to satisfy both Pari and Arya.
大體題意：
給你一個無向圖，判斷是否能夠構成一個二分圖，如果能的話，輸出二分圖左邊的集合和右邊的集合。
思路：
通過這個題目學習了二分圖染色法，靜下心來感覺并不難。
先給每一個頂點的color設定為-1，表示沒有被染色，用vector數組v[a]，表示元素a所相連的全部元素。
然後枚舉每一個頂點，發現沒有被染色，就對他進行染色，先把頂點染成0，然後再0顔色的vector加入目前元素，在枚舉與這個元素相連的元素，假設顔色是c的話，相連的就染成c^1，這個方法會把0變成1，1變成0，因為二分圖氛圍左邊和右邊，就可以這麼了解，左邊是0，右邊是1，在dfs中發現該元素已被染色就return，發現染色的顔色與該染的顔色不符合，就不能構成二分圖了，ok=false。
有個小小的剪枝，發現ok已經false了 直接return了。這樣會快一定的速度。
詳細見代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 100000 + 10;
vector<int>g[maxn],v[2];
bool ok = true;
int color[maxn];
void dfs(int k,int c){
if(!ok)return;
if (color[k] != -1){
if (color[k] != c)ok=false;
return;
}
color[k] = c;
v[c].push_back(k);
int len = g[k].size();
for (int i = 0; i < len; ++i)dfs(g[k][i],c^1); // 0 -> 1,, 1 -> 0;
}
void print(vector<int> & t){
int len = t.size();
printf("%d\n",len);
for (int i = 0; i < len; ++i){
if (i)printf(" ");
printf("%d",t[i]);
}
printf("\n");
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < m; ++i){
int u,w;
scanf("%d%d",&u,&w);
g[u].push_back(w);
g[w].push_back(u);
}
memset(color,-1,sizeof color);
for (int i = 1; i <= n; ++i){
if (color[i] == -1)dfs(i,0);
}
if (!ok)printf("-1\n");
else {
for (int i = 0; i < 2; ++i)print(v[i]);
}
return 0;
}