#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
const int MAXE=10000002;
const int MAX=20009;
int vis[10009];
struct Point
{
int x,y;
}p[10009];
struct EDGE
{
int v; // 从u点出发能到达的点v
int next; // 从u点出发能到达的下一条边的编号
}edge[MAXE];
int first[MAX]; // first[u] = e:从点u出发的最后一条边的编号是e(“最后”是指最后输入)
int dfn[MAX]; // dfn[u]:节点u搜索的次序编号(时间戳)
int low[MAX];// low[u]:是u或u的子树能够追溯到的最早的栈中节点的次序号
int ins[MAX];// 是否在栈中
int scc[MAX]; // scc[i] = j:第i个点所在的强连通分量的编号 (此题可有可无)
int t,n,m;
int num; // 强连通分量的数目
int index; // 次序编号
int s[MAX];
int top,e;
int a,b,c,d,nn;
int DFS(int x)
{
low[x]=dfn[x]=index++;
s[++top]=x;
ins[x]=1;
// 枚举每一条边:u-->v
for(int k=first[x];k!=-1;k=edge[k].next)
{
int v=edge[k].v;
if(dfn[v]==0)
{
DFS(v);
low[x]=min(low[x],low[v]);
}
else if(ins[v])
{
low[x]=min(dfn[v],low[x]);
}
}
// 如果节点u是强连通分量的根
if(low[x]==dfn[x])
{
int v;
num++;
do{
v=s[top--];
ins[v]=0;
scc[v]=num;
}while(v!=x);
}
return 1;
}
inline void add(int u,int v)
{
edge[e].v=v;
edge[e].next=first[u];
first[u]=e++;
}
inline int turn(int x)
{
return x>n?x-n:x+n;
}
void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(first,-1,sizeof(first));
// memset(ins,0,sizeof(ins));
index=1;
top=-1;
num=0;
e=0;
int a,b,c;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c==0)
{
if(p[a].x!=p[b].x)
{
add(a,b+n);
add(b,a+n);
}
if(p[a].x!=p[b].y)
{
add(a,b);
add(b+n,a+n);
}
if(p[a].y!=p[b].x)
{
add(a+n,b+n);
add(b,a);
}
if(p[a].y!=p[b].y)
{
add(a+n,b);
add(b+n,a);
}
}
else
{
if(p[a].x==p[b].x)
{
add(a,b+n);
add(b,a+n);
}
if(p[a].x==p[b].y)
{
add(a,b);
add(b+n,a+n);
}
if(p[a].y==p[b].x)
{
add(a+n,b+n);
add(b,a);
}
if(p[a].y==p[b].y)
{
add(a+n,b);
add(b+n,a);
}
}
}
}
bool check()
{
for(int i=1;i<=n;i++)
if(scc[i]==scc[i+n])
return false;
return true;
}
void solve(int ii)
{
for(int i=1;i<=2*n;i++)
{
if(dfn[i]==0)
{
DFS(i);
}
}
printf("Case #%d: ",ii);
if(check())puts("yes");
else puts("no");
}
int main()
{
int ca,a;
scanf("%d",&ca);
for(int ii=1;ii<=ca;ii++)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&vis[i]);
if(vis[i]==1)
{
p[i].x=1;
p[i].y=2;
}
if(vis[i]==2)
{
p[i].x=2;
p[i].y=3;
}
if(vis[i]==3)
{
p[i].x=3;
p[i].y=1;
}
}
init();
solve(ii);
}
return 0;
}
更多推荐
HDU 4115 Eliminate the Conflict 2-sat
发布评论