问题描述

判断一个包含n对男女关系的图中是否存在矛盾，若存在矛盾则输出"Unsafe"，否则输出"Safe"。

解题思路

使用Tarjan算法求解强连通分量（SCC），将每个男孩和女孩视为2-SAT问题中的变量及其否定，通过检查每个男孩与对应女孩是否在同一SCC中判断是否存在矛盾。

#include<bits/stdc++.h>using namespace std;
const int N=1e4+10;vector<int>G[N];map<string,int>id;
int tsp,cnt,dfn[N],low[N],scc[N];stack<int>stk;bool instk[N];

void tarjan(int x){
    dfn[x]=low[x]=++tsp;stk.push(x);instk[x]=1;
    for(int y:G[x]){
        if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}
        else if(instk[y]){low[x]=min(low[x],dfn[y]);}
    }
    if(dfn[x]==low[x]){
        ++cnt;
        for(int z=-1;z!=x;){
            z=stk.top();stk.pop();instk[z]=0;scc[z]=cnt;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;string girl,boy;
    for(int i=1;i<=n;++i){
        cin>>girl>>boy;id[boy]=i;id[girl]=i+n;G[i+n].push_back(i);
    }
    int m;cin>>m;
    for(int i=1,x,y;i<=m;++i){
        cin>>girl>>boy;x=id[boy],y=id[girl];G[x].push_back(y);
    }
    tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
    for(int i=1;i<=2*n;++i)if(!dfn[i])tarjan(i);
    
    for(int i=1;i<=n;++i)cout<<(scc[i]==scc[i+n]?"Unsafe\n":"Safe\n");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
vector<int>G[N];
map<string,int>id; 
int tsp,cnt,dfn[N],low[N],scc[N];
stack<int>stk;bool instk[N];
void tarjan(int x)
{
	dfn[x]=low[x]=++tsp;
	stk.push(x);instk[x]=1; 
	for(int y:G[x])
	{
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(instk[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		++cnt;
		for(int z=-1;z!=x;)
		{
			z=stk.top();stk.pop();instk[z]=0;
			scc[z]=cnt;
		}
	}
}
 
int main()
{
    ios::sync_with_stdio(False);cin.tie(0);cout.tie(0);
	int n;cin>>n;
    string girl,boy;
	for(int i=1;i<=n;i++)
	{
		cin>>girl>>boy;
		id[boy]=i;id[girl]=i+n;
		G[i+n].push_back(i);
	}
	int m;cin>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>girl>>boy;
		x=id[boy],y=id[girl];
		G[x].push_back(y);
	}
	tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
	for(int i=1;i<=n*2;++i) if(!dfn[i]) tarjan(i);
	
	for(int i=1;i<=n;++i)
		if(scc[i]==scc[i+n]) cout<<"Unsafe\n";
		else cout<<"Safe\n";
	return 0;
}