hdu1814 Peaceful Commission--dfs

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=1814​​

题意：n个党派参加会议，每个党派有2名代表，且每个党派必须只能派一个人去，但是有m对人是有仇的，他们不能同时参加会议。如果可以让n个党派都有人参加，升序输出派的人的编号，不然输出NIE。

这题应该用2-sat算法求解，不过这题暴力直接dfs也可以。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

int n, m;
vector<int> vec[8000 * 2 + 10];
bool vis[8000 * 2 + 10];
int sta[8000 * 2 + 10];
int top;

bool dfs(int x)
{
  if (vis[x ^ 1])
    return false;
  if (vis[x])
    return true;

  vis[x] = 1;
  sta[top++] = x;
  for (int i = 0; i < vec[x].size(); i++)
    if (!dfs(vec[x][i]))
      return false;
  return true;
}

bool solve()
{
  for (int i = 0; i < 2 * n; i=i+2)
  {
    if (!vis[i] && !vis[i ^ 1])
    {
      top = 0;
      if (!dfs(i))
      {
        while (top > 0)
          vis[sta[--top]] = 0;
        if (!dfs(i + 1))
          return false;
      }
    }
  }
  return true;
}


int main()
{
  while (~scanf("%d%d", &n, &m))
  {
    for (int i = 0; i < 2 * n; i++)
    {
      vis[i] = 0;
      vec[i].clear();
    }
    
    int x, y;
    while (m--)
    {
      scanf("%d%d", &x, &y);
      x--;
      y--;
      vec[x].push_back(y ^ 1);
      vec[y].push_back(x ^ 1);
    }

    if (!solve())
      printf("NIE\n");
    else
    {
      for (int i = 0; i < 2 * n; i++)
        if (vis[i])
          printf("%d\n", i + 1);
    }
  }

  return 0;
}