CodeForces 687A NP-Hard Problem （二分图）

题意：给定 n 条边，然后让你把它分成两组，每组都有所有边的一个端点。

析：一开始我是先判定环，以为就不能成立，其实不是这样的，有环也行。用dfs进行搜索，并标记每一个端点，如果标记过并且和以前不一样，那么就是不能成立，

否则就能成立，并且标记上。最后分类输出就好。

代码如下：

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
vector<int> G[maxn];
vector<int> a, b;
int vis[maxn];
bool ok = true;

 void dfs(int val, int i){
    if(!vis[i]) vis[i] = val;//没有标记的标记上
    else if(vis[i] != val){  ok =false;  return ; }//如果标记不一样，那就不能标记
    else  return ;
    for(int j = 0; j < G[i].size(); ++j){
        dfs(val == 1 ? 2 : 1, G[i][j]);//搜索
    }
 }

void print(vector<int> &x, vector<int> &y){//输出
    printf("%d
", x.size());
    for(int i = 0; i < x.size(); ++i) if(!i) printf("%d", x[i]);
    else printf(" %d", x[i]);
    printf("
%d
", y.size());
    for(int i = 0; i < y.size(); ++i) if(!i) printf("%d", y[i]);
    else printf(" %d", y[i]);
    printf("
");
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    memset(vis, 0, sizeof(vis));
    int u, v;
    for(int i = 0; i < m; ++i){
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for(int i = 1; i <= n; ++i)
        if(!vis[i] && !G[i].empty())  dfs(1, i);
    for(int i = 1; i <= n; ++i)  if(vis[i] == 1)  a.push_back(i);
    else if(vis[i] == 2)  b.push_back(i);
    if(ok)  print(a, b); else printf("-1
");
    return 0;
}