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

$互斥的点加一条边$

$缩点后,保证互的点不在一个强连通内$

$就可以拓扑排序$

$scc编号小的拓扑序号反而大(也就是先进行拓扑)$

$我们需要的就是拓扑号大的,这样对后续影响小$

#include 
   
    using namespace std;const int maxn=4e6+10;int n,m;struct edge{	int to,nxt;}d[maxn]; int head[maxn],cnt;void add(int u,int v){	d[++cnt]=(edge){v,head[u]},head[u]=cnt;}int low[maxn],dfn[maxn],vis[maxn],scc[maxn],stac[maxn],id,top,scc_num;/*void tarjan(int u,int fa){	dfn[u]=low[u]=++id;	stac[++top]=u,vis[u]=1;	for(int i=head[u];i;i=d[i].nxt )	{		int v=d[i].to;		if( v==fa )	continue;		if( !dfn[v] )				tarjan(v,u), low[u]=min( low[u],low[v] );		else if( vis[v] )			low[u]=min( low[u],dfn[v] );	}	if( dfn[u]==low[u] )	{		scc_num++;		while( stac[top]!=u )		{			scc[ stac[top] ]=scc_num;			vis[ stac[top] ]=0;			top--;		}		scc[ stac[top] ]=scc_num;		vis[ stac[top] ]=0;		top--;	}}*/void tarjan(int u,int fa){    dfn[u]=low[u]=++id;    stac[++top]=u;    vis[u]=1;    for(int i=head[u];i;i=d[i].nxt)    {        int v=d[i].to;        if(v==fa) continue;        if(!dfn[v])        {            tarjan(v,u);            low[u]=min(low[u],low[v]);        }        else if(vis[v]) low[u]=min(low[u],dfn[v]);    }    if(dfn[u]==low[u])    {        scc_num++;        while(stac[top]!=u)        {            scc[stac[top]]=scc_num;            vis[stac[top]]=0;            top--;        }        scc[stac[top]]=scc_num;        vis[stac[top]]=0;        top--;    }}int main(){	ios::sync_with_stdio(false);	cin >> n >> m;	for(int i=1;i<=m;i++)	{		int a,x,b,y;//a+n表示1 		cin >> a >> x >> b >> y;		if( x==0&&y==0 )	add(a+n,b),add(b+n,a);		if( x==0&&y==1 )	add(a+n,b+n),add(b,a);		if( x==1&&y==0 )	add(a,b),add(b+n,a+n);		if( x==1&&y==1 )	add(a,b+n),add(b,a+n);	}	for(int i=1;i<=2*n;i++)		if( !dfn[i] )	tarjan(i,0);	for(int i=1;i<=n;i++)		if( scc[i]==scc[i+n] )		{			cout << "IMPOSSIBLE\n";			return 0;		}	cout << "POSSIBLE\n";	for(int i=1;i<=n;i++)	{		if( scc[i]>scc[i+n] )	cout << 1 << " ";//强连通编号小->拓扑序越大(比较容易拓扑出来) 		else	cout << 0 << " ";	}}
   

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