本文共 2141 字，大约阅读时间需要 7 分钟。

每个代表要么被选中,要么不被选中,标记为$true$或$false$

为了方便,规定$x$为$true$时编号$x$,为$false$时编号$x+base$

对于相互厌恶的$u,v$来说$u,v$不能同时为$true$

若$u=true$则$v=false$,连边$(u,v+base)$

若$v=true$则$u=false$,连边$(v,u+base)$

对于属于一个党派的代表$u,v$来说恰好有一个为$true$

若$u=true$则$v=false$

若$u=false$则$v=true$

若$v=true$则$u=false$

若$v=false$则$u=true$

这样连边,跑$2-SAT$即可

但是仔细观察发现可以优化,因为$i\ast 2-1$和$i\ast 2$的关系一定是对立的

厌恶的两个人$l,r$关系也是对立的,我们只需要彼此连边就可以,最后只要不在一个连通分量即可,不需要提前确定哪个点是$true,false$

每次选择拓扑序大的就好了

#include 
   
    using namespace std;const int maxn = 3e6+10;struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt] = ( edge ){
   v,head[u]},head[u] = cnt;}int n,m,base;int dfn[maxn],low[maxn],stac[maxn],vis[maxn],scc[maxn],sc,id,top;void tarjan(int u){
   	vis[u] = 1, stac[++top] = u, low[u] = dfn[u] = ++id;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( !dfn[v] )		{
   			tarjan(v);			low[u] = min( low[u],low[v] );		}		else if( vis[v] )			low[u] = min( low[u],dfn[v] );	}	if( low[u]==dfn[u] )	{
   		sc++; int temp;		while( temp = stac[top--] )		{
   			scc[temp] = sc, vis[temp] = 0;			if( temp == u )	break;		}	}}int ok[maxn];int main(){
   	cin >> n >> m; base = n+n;	for(int i=1;i<=n;i++)	{
   		int u = i*2-1, v = u+1;		add(u,v+base); add(u+base,v);		add(v,u+base); add(v+base,u);	}	for(int i=1;i<=m;i++)	{
   		int l,r; scanf("%d%d",&l,&r);		add(l,r+base); add(r,l+base);	}	for(int i=1;i<=n+n+base;i++)		if( !dfn[i] )	tarjan(i);	for(int i=1;i<=n+n;i++)	{
   		if( scc[i]==scc[i+base] ){
    puts("NIE"); return 0; }		if( scc[i]>scc[i+base] )	ok[i] = 2;//false		else	ok[i] = 1;//true	}	for(int i=1;i<=n+n;i++)		if( ok[i]==1 )	cout << i << endl;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115428004 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！