洛谷1407 [国家集训队]稳定婚姻

语文阅读题

题意

有 $n(\le 4000)$ 对夫妻，还有 $m(\le 20000)$ 对此前的交往关系（都是在这 $2n$ 个人之间）。如果某对夫妻吵架，那么他们都会找此前交往的人复合，然后又一对夫妻被拆散……

如果某对夫妻吵架，发生上述过程后可以组成新的婚姻关系，那么就称该婚姻不稳定；否则稳定。询问每个婚姻是否为稳定婚姻。

题解

先考虑吵架后丈夫的行为，可以发现关系的传递是 男 $\rightarrow$ 女 $\rightarrow$ 男 $\rightarrow$ ……如果形成一个环就不稳定。

所以把夫妻关系按 女 $\rightarrow$ 男 的顺序连边，交往关系则按 男 $\rightarrow$ 女的关系连。然后跑一遍 $\text{Tarjan}$ ，判断夫妻关系的两人是否在同一强连通分量即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N=8005,M=48005;
struct node {
    int next,to;
} edge[M];
string a,b;
stack <int> s;
map <string,int> mp;
int cnt,head[N],n,m,scnt,dfsord,id[N],low[N],scc[N];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    s.push(x);
    id[x]=low[x]=++dfsord;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            if (t==x) break;
        }
    }
}

signed main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a>>b;
        mp[a]=i*2-1; mp[b]=i*2;
        add(mp[a],mp[b]); //女->男
    }
    cin>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>a>>b;
        add(mp[b],mp[a]); //男->女
    }
    for (int i=1;i<=n*2;i++) if (!id[i]) dfs(i);
    for (int i=1;i<=n;i++)
    {
        if (scc[i*2-1]==scc[i*2]) puts("Unsafe");
        else puts("Safe");
    }
    return 0;
}