学步园

简单2-sat

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 405
#define M 10010
using namespace std;
int a[M],b[M],c[M];
struct Edge{
    int v,next;
}edge[M*2];
int head[N],cnt,scc,top,Index;
int dfn[N],low[N],instack[N],sstack[N],belong[N];

void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void tarjan(int u){
    dfn[u]=low[u]=++Index;
    sstack[++top]=u;
    instack[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[v],low[u]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc++;
        while(1){
            int tmp=sstack[top--];
            instack[tmp]=0;
            belong[tmp]=scc;
            if(tmp==u)break;
        }
    }
}
void init(){
    memset(head,-1,sizeof(head));
    cnt=Index=top=scc=0;
    memset(instack,0,sizeof(instack));
    memset(dfn,0,sizeof(dfn));
}
int main(){
    int t,T;
    int i,j;
    int n,m;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d %d",&n,&m);
        for(i=1;i<=m;i++)
            scanf("%d %d %d",&a[i],&b[i],&c[i]);
        int l=0,h=m,ans;
        while(l<=h){
            int mid=(l+h)>>1;
            init();
            for(i=1;i<=mid;i++){
                if(c[i]==0){
                    addedge(a[i]*2+2-1,b[i]*2+2);
                    addedge(b[i]*2+2-1,a[i]*2+2);
                }
                else if(c[i]==1){
                    addedge(a[i]*2+2-1,b[i]*2-1+2);
                    addedge(a[i]*2+2,b[i]*2+2);
                    addedge(b[i]*2+2-1,a[i]*2-1+2);
                    addedge(b[i]*2+2,a[i]*2+2);
                }
                else{
                    addedge(a[i]*2+2,b[i]*2+2-1);
                    addedge(b[i]*2+2,a[i]*2+2-1);
                }
            }
            for(i=1;i<=2*n;i++){
                if(!dfn[i])
                    tarjan(i);
            }
            bool flag=1;
            for(i=1;i<=n;i++)
                if(belong[i*2-1]==belong[i*2]){
                    flag=0;
                    break;
                }
            if(flag){
                l=mid+1;
                ans=mid;
            }
            else h=mid-1;
        }
        printf("%d\n",ans);
    }
}