hdu3715 Go Deeper--二分 & 2-sat

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

题意：有一个递归代码：
go(int dep, int n, int m)
begin
     output the value of dep.
     if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end 
关键是看第四行， 如果满足条件dep < m and x[a[dep]] + x[b[dep]] != c[dep] 那么就可以进入下一层递归， x数组只取{0, 1}， c数组取{ 0，1，2 }, 而a和b数组取0～m， m是最大能递归的层数，也是数组x的大小。  问最多能递归多少层？

分析：

如果给出的c[i]为0时，那么x[a[i]]和x[b[i]]中的其中一个要为真，连边即为 !a[i]->b[i], !b[i] -> a[i]
如果给出的c[i]为1时，那么x[a[i]]和x[b[i]]两个要么都为真，要么都为假，连边即为a[i]->b[i], b[i]->a[i], !a[i]->!b[i], !b[i]->!a[i]
如果给出的c[i]为2时，那么x[a[i]]和x[b[i]]两个中的一个要为假 ，连边即为a[i]->!b[i], b[i]->!a[i]

#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 t;
int n, m;
int index, cnt;
int a[20005], b[20005], c[20005];
bool inStack[405];
int low[405];
int dfn[405];
int belong[405];
vector<int> vec[405];
stack<int> s;


void init()
{
  cnt = index = 0;
  for (int i = 0; i < 2 * n; i++)
  {
    vec[i].clear();
    inStack[i] = 0;
    dfn[i] = 0;
  }
}

void tarjan(int u)
{
  low[u] = dfn[u] = ++index;
  inStack[u] = 1;
  s.push(u);
  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i];
    if (!dfn[v])
    {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    }
    else if (inStack[v])
      low[u] = min(low[u], dfn[v]);
  }

  if (low[u] == dfn[u])
  {
    int p;
    cnt++;
    do
    {
      p = s.top();
      s.pop();
      inStack[p] = 0;
      belong[p] = cnt;
    } while (p != u);
  }
}

bool solve()
{
  for (int i = 0; i < 2 * n; i++)
    if (!dfn[i])
      tarjan(i);
  for (int i = 0; i < n; i++)
    if (belong[i] == belong[i + n])//注意这里，不是i+1
      return false;
  return true;
}

void build(int dep)
{
  init();
  for (int i = 0; i < dep; i++)
  {
    int x = a[i];
    int y = b[i];
    if (c[i] == 0)
    {
      vec[x].push_back(y + n);
      vec[y].push_back(x + n);
    }
    else if (c[i] == 1)
    {
      vec[x].push_back(y);
      vec[y].push_back(x);
      vec[x + n].push_back(y + n);
      vec[y + n].push_back(x + n);
    }
    else if (c[i] == 2)
    {
      vec[x + n].push_back(y);
      vec[y + n].push_back(x);
    }
  }
}

int main()
{
  scanf("%d", &t);
  while (t--)
  {
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++)
      scanf("%d%d%d", &a[i], &b[i], &c[i]);

    int l = 1;
    int r = m;
    int mid;
    while (l <= r)
    {
      mid = (l + r) / 2;
      build(mid);
      if (solve())
        l = mid + 1;
      else
        r = mid - 1;
    }

    printf("%d\n", l - 1);
  }

  return 0;
}