2-SAT+二分，X[ ]每个元素可以为0或1，是否存在这样的数组让程序的输出值最大，
明显的2-SAT，要求最大值就得二分验证，刚开始脑子抽筋的想到只需要前mid出现的X[]满足就可以，
验证的时候写成i<mid，果断wrong了。前mid出现的X[]的下标肯定不是连续的，
所以就只要验证前mid出现的X[]就行了，果然AC。
今天早上看了看程序，发现前mid没出现的X[ ]，根本就没有加边，所以肯定会满足，所以也可以验证到n。
#include<stdio.h>
#include<string.h>
#include<stack>
#define N 500
using namespace std;
struct node
{
int ed,next;
}E[N*N];
struct op
{
int a,b,c;
}q[10010];
int n,m,low[N],dfs[N],belong[N],ins[N],first[N],num,ans,idx;
void addeage(int x,int y)
{
E[num].ed=y;
E[num].next=first[x];
first[x]=num++;
}
void insit()
{
memset(dfs,-1,sizeof(dfs));
memset(low,0,sizeof(low));
memset(first,-1,sizeof(first));
memset(belong,0,sizeof(belong));
ans=idx=num=0;
}
stack<int>Q;
void Tarjan(int x)
{
int v;
low[x]=dfs[x]=idx++;
ins[x]=1;
Q.push(x);
for(int p=first[x];p!=-1;p=E[p].next)
{
v=E[p].ed;
if(dfs[v]==-1)
{
Tarjan(v);
low[x]=low[x]>low[v]?low[v]:low[x];
}
else if(ins[v]==1)
{
low[x]=low[x]>dfs[v]?dfs[v]:low[x];
}
}
if(dfs[x]==low[x])
{
ans++;
do
{
v=Q.top();
Q.pop();
belong[v]=ans;
ins[v]=0;
}while(v!=x);
}
}
int judge(int d)
{
insit();
int i;
for(i=0;i<d;i++)
{
if(q[i].c==0)
{
addeage(q[i].a,q[i].b+n);
addeage(q[i].b,q[i].a+n);
}
else if(q[i].c==1)
{
addeage(q[i].a+n,q[i].b+n);
addeage(q[i].b,q[i].a);
addeage(q[i].b+n,q[i].a+n);
addeage(q[i].a,q[i].b);
}
else if(q[i].c==2)
{
addeage(q[i].a+n,q[i].b);
addeage(q[i].b+n,q[i].a);
}
}
for(i=0;i<2*n;i++)
{
if(dfs[i]==-1)
Tarjan(i);
}
/*
for(i=0;i<d;i++)
{
if(belong[q[i].a]==belong[q[i].a+n])
return 0;
if(belong[q[i].b]==belong[q[i].b+n])
return 0;
}*/
for(i=0;i<n;i++)
{
if(belong[i]==belong[i+n])
return 0;
}
return 1;
}
int main()
{
int i,mid,t,min,max,mmax;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);
min=0;max=m;mmax=min;
while(min<=max)
{
mid=(min+max)/2;
if(judge(mid))
{
if(mmax<mid)mmax=mid;
min=mid+1;
}
else max=mid-1;
}
printf("%d\n",mmax);
}
return 0;
}