学步园

题目链接：Click here~~

题意：

给一个递归函数，问最多递归到第几层。

解题思路：

2-SAT + 二分，应该很经典。贴一个出来。

只有数组 x[ ] 是未知的，而且 x[i] 的取值只有 0 和 1，把它们看做 i 和 i'。

对于某一个层数 dep ，若 dep 存在，就要满足 x[ a[i] ] + x[ b[i] ] != c[i]（i∈[0,dep-1]）。

所以，那些不满足这个条件的就为冲突。

根据冲突关系连边。二分即可。

#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 405;
const int M = 40013;

struct Vertex
{
    int head;
}V[N],VV[N];

struct Edge
{
    int v,next;
}E[M],EE[M];

int top,topp,scc,id,dfn[N],low[N],ind[N],belong[N];

bool in[N],vis[N],color[N];

stack<int> S;

void init()
{
    top = topp = 0;
    memset(V,-1,sizeof(V));
    memset(VV,-1,sizeof(VV));
}

void add_edge(int u,int v)
{
    E[top].v = v;
    E[top].next = V[u].head;
    V[u].head = top++;
}

void add_edge2(int u,int v)
{
    EE[topp].v = v;
    EE[topp].next = VV[u].head;
    VV[u].head = topp++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++id;
    S.push(u);
    in[u] = true;
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v = E[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        int v;
        do
        {
            v = S.top();
            S.pop();
            in[v] = false;
            belong[v] = scc;
        }while(u != v);
        scc++;
    }
}

void get_scc(int n)
{
    scc = id = 0;
    memset(dfn,0,sizeof(dfn));
    memset(in,false,sizeof(in));
    for(int i=0;i<n;i++)
        if(!dfn[i])
            tarjan(i);
}

bool conflict(int n)
{
    for(int i=0;i<n;i++)
        if(belong[i<<1] == belong[i<<1|1])
            return true;
    return false;
}

int a[10005],b[10005],c[10005];

int main()
{
    //freopen("in.ads","r",stdin);
    int T,n,m;
    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 = 0 , r = m+1;
        while(l < r)
        {
            init();
            int mid = l+r >> 1;
            for(int i=0;i<mid;i++)
            {
                int u = a[i]<<1 , v = b[i]<<1;
                if(c[i] == 0)
                {
                    add_edge(u,v^1);
                    add_edge(v,u^1);
                }
                else if(c[i] == 1)
                {
                    add_edge(u,v);
                    add_edge(u^1,v^1);
                    add_edge(v,u);
                    add_edge(v^1,u^1);
                }
                else
                {
                    add_edge(u^1,v);
                    add_edge(v^1,u);
                }
            }
            get_scc(n<<1);
            if(conflict(n))
                r = mid;
            else
                l = mid+1;
        }
        printf("%d\n",r-1);
    }
    return 0;
}