codeforces 688c 二分图判断

In the first sample, you can give the vertex number 2 to Arya and vertices numbered1 and 3 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.

题意：给你一些顶点和边，让你把他们分成两个组，并且同组内顶点不能有边连接

思路：直接二分图，dfs/bfs来判断，首先分成两组嘛，那就是给这两组进行染色，如果出息你属于同一组的那么一定不是二分图，然后一组染色为1，另一组染色为2进行判断

DFS写法：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
int vist[100030],flag,val[100030],n,m;
vector <int>v[100030];
void dfs(int i,int va) {
vist[i] = 1;
val[i] = va;
for(int j = 0; j < (int)v[i].size(); j++) {
if(!vist[v[i][j]]) {
dfs(v[i][j],3-va);
} else if(val[v[i][j]] == va) {
flag = 1;
return;
}
}
}
int main() {
cin >> n >> m;
memset(vist,0,sizeof(vist));
memset(val,-1,sizeof(val));
while(m--) {
int x,y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
flag = 0;
for(int i = 1;i<= n;i++){
if(val[i] == -1){
dfs(i,1);
}
if(flag){
break;
}
}
if(flag == 1) {
cout << "-1" <<endl;
} else {
int tot = 0;
for(int i = 1; i <= n; i++) {
if(val[i] == 1) {
tot++;
}
}
cout << tot << endl;
for(int i = 1; i <= n; i++) {
if(val[i] == 1) {
cout << i << " ";
}
}
tot = 0;
for(int i = 1; i <= n; i++) {
if(val[i] == 2) {
tot++;
}
}
cout <<endl <<
tot << endl;
for(int i = 1; i <= n; i++) {
if(val[i] == 2) {
cout << i << " ";
}
}
cout << endl;
}
return 0;
}

#include<iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
int color[100030];
vector < int > mp[100030];
int n,m;
int bfs(int ss) {
color[ss] = 1;
queue<int>s;
s.push(ss);
while(!s.empty()) {
int u = s.front();
s.pop();
int len=mp[u].size();
for(int i = 0; i < len; i++) {
int v = mp[u][i];
if(u == v)continue;
if(color[v] == -1) {
color[v] = 3-color[u];
s.push(v);
} else {
if(color[u] == color[v]) {
return 0;
}
}
}
}
return 1;
}
int main() {
cin >> n >> m;
memset(color,-1,sizeof(color));
for(int i = 0;i < m;i++){
int x,y;
cin >> x >> y;
mp[x].push_back(y);
mp[y].push_back(x);
}
int tt = 1;
for(int i = 1;i<= n;i++){
if(color[i] == -1){
int ttt = bfs(i);
if(ttt == 0){
tt = 0;
break;
}
}
}
if(tt == 0){
cout << "-1" << endl;
}else{
int tot = 0;
for(int i = 1;i <= n;i++){
if(color[i] == 1){
tot++;
}
}
cout << tot << endl;
for(int i = 1;i <= n;i++){
if(color[i] == 1){
cout << i << " ";
}
}
tot = 0;
for(int i = 1;i <= n;i++){
if(color[i] == 2){
tot++;
}
}
cout <<endl <<
tot << endl;
for(int i = 1;i <= n;i++){
if(color[i] == 2){
cout << i << " ";
}
}
cout << endl;
}
return 0;
}