内江网站开发0832hdsj,wordpress 4.4 下载,php模板网站,dedecms是什么意思正题
题目链接:https://www.luogu.com.cn/problem/P4782 题目大意
给若干个条件限定为xi为a或xj为bx_i为a或x_j为bxi为a或xj为b。求构造一个序列xxx满足所有条件 解题思路
我们对于每个xix_ixi构造两个点分别表示xix_ixi为0/10/10/1。然后就开始对能够确定的条件关系…正题
题目链接:https://www.luogu.com.cn/problem/P4782 题目大意
给若干个条件限定为xi为a或xj为bx_i为a或x_j为bxi为a或xj为b。求构造一个序列xxx满足所有条件 解题思路
我们对于每个xix_ixi构造两个点分别表示xix_ixi为0/10/10/1。然后就开始对能够确定的条件关系连边。那么显然有在一个强连通分量里的真假一定相等。也就是如果对于一个xix_ixi的两个点都在一个强连通里那么就无解了。
而确定之后我们只需要根据拓扑序大小来确定真假即可。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N2e610;
struct node{int to,next;
}a[N*2];
int n,m,tot,cnt,num,ls[N];
int dfn[N],low[N],color[N];
bool ins[N];
stackint S;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void tarjan(int x){dfn[x]low[x]cnt;S.push(x);ins[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(!dfn[y])tarjan(y),low[x]min(low[x],low[y]);else if(ins[y]) low[x]min(low[x],dfn[y]);}if(low[x]dfn[x]){num;while(S.top()!x){ins[S.top()]0;color[S.top()]num;S.pop();}color[S.top()]num;ins[S.top()]0;S.pop();}return;
}
int main()
{scanf(%d%d,n,m);for(int k1;km;k){int i,a,j,b;scanf(%d%d%d%d,i,a,j,b);addl(ia*n,j(!b)*n);addl(jb*n,i(!a)*n);}for(int i1;in*2;i)if(!dfn[i])tarjan(i);for(int i1;in;i)if(color[i]color[in]){printf(IMPOSSIBLE);return 0;}printf(POSSIBLE\n);for(int i1;in;i)printf(%d ,color[i]color[in]);
}
