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\n", x.size());

    for(int i = 0; i < x.size(); ++i) if(!i) printf("%d", x[i]);

    else printf(" %d", x[i]);

    printf("\n%d\n", y.size());

    for(int i = 0; i < y.size(); ++i) if(!i) printf("%d", y[i]);

    else printf(" %d", y[i]);

    printf("\n");

}

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\n");

    return 0;

}