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

这个题面很有意思，像我这样的菜鸡，完全不需考虑婚姻的稳定 性 问题。

tarjan裸题，直接讲算法吧：

原配夫妻之间分别连一条边，小情人之间反向连边。

这时候我们会发现一个性质，如果婚姻稳定，那么夫妻之间肯定不在一个强连通分量中，反之，在一个强连通分量中的夫妻就是Unsafe的。

代码：

#include <bits/stdc++.h>

using namespace std;

stack <int> ss;

const int N=200010;

map <string,int> mp;

int n,m,s[N][2],o[N],cnt;

int low[N],dfn[N],dfscnt,scc,sccno[N];

void add(int x,int y)

{

    s[++cnt][0]=y;

    s[cnt][1]=o[x];

    o[x]=cnt;

}

void tarjan(int x)

{

    ss.push(x);

    low[x]=dfn[x]=++dfscnt;

    for (int i=o[x];i;i=s[i][1]) {

        if (!dfn[s[i][0]]) {

            tarjan(s[i][0]);

            low[x]=min(low[x],low[s[i][0]]);

        }

        else if (!sccno[s[i][0]])

        low[x]=min(low[x],dfn[s[i][0]]);

    }

    if (dfn[x]==low[x]) {

        scc++;

        while (1) {

            int y=ss.top();

            sccno[y]=scc;

            ss.pop();

            if (x==y) break;

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin>>n;string a,b;

    for (int i=1;i<=n;i++) {

        cin>>a>>b;

        mp[a]=i;

        mp[b]=i+n;

        add(i,i+n);

    }

    cin>>m;

    for (int i=1;i<=m;i++) {

        cin>>a>>b;

        add(mp[b],mp[a]);

    }

    m=n<<1;

    for (int i=1;i<=m;i++)

    if (!dfn[i])

    tarjan(i);

    for (int i=1;i<=n;i++)

    if (sccno[i]==sccno[i+n])

    cout<<"Unsafe\n";

    else cout<<"Safe\n";

    return 0;

}

巴特西

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

最新文章

热门文章