BZOJ 2140安定結婚

タイトルリンク:http://61.187.179.132/JudgeOnline/problem.php?id=2140
标题:n組の夫婦の結婚状況が知られており、第i組の夫婦の男性をBi、女性をGiと呼ぶ.ある男性Biがある女性Gjと付き合ったことがある場合、ある配偶者(すなわちBiとGiまたはBjとGj)との感情に問題が発生した場合、BiとGjは駆け落ちする可能性がある.Biとその配偶者Giの感情が合わないとして、BiとGjの旧情が再燃し、さらにBjは緑の帽子をかぶって不快になり、初恋の恋人Gkに連絡した......一連の離婚事件がドミノの骨牌のように相次いだ.BiとGiが離婚した前提の下で、この2 n人は最終的にn対のカップルに結合することができれば、私たちは結婚iを安全ではないと呼んでいます.そうしないと、結婚iは安全です.必要な情報を与えて、あなたの任務は結婚が安全かどうかを判断することです.
考え方:夫婦を一つの点と見なして、付き合ったことのある二つの点の両側.強い連通成分を求めて、強い連通成分の中の個数が1より大きいのは安全ではありません
 

map<string,int> mp1,mp2;

vector<int> g[N];

int n,m;

int low[N],dfn[N],id,color[N],size[N],num;

stack<int> S;

int visit[N];





void DFS(int u)

{

    dfn[u]=low[u]=++id;

    S.push(u);

    

    int i,v;

    FOR0(i,SZ(g[u]))

    {

        v=g[u][i];

        if(!dfn[v]) DFS(v),upMin(low[u],low[v]);

        else if(!visit[v]) upMin(low[u],dfn[v]);

    }

    if(low[u]==dfn[u])

    {

        num++;

        do

        {

            v=S.top();

            S.pop();

            visit[v]=1;

            color[v]=num;

            size[num]++;

        }while(u!=v);

    }

}





int main()

{

    RD(n);

    string S;

    int i;

    FOR1(i,n)

    {

        RD(S); mp1[S]=i;

        RD(S); mp2[S]=i;

    }

    RD(m);

    int x,y;

    FOR1(i,m)

    {

        RD(S); x=mp1[S];

        RD(S); y=mp2[S];

        g[x].pb(y); 

    }

    FOR1(i,n) if(!visit[i]) DFS(i);

    FOR1(i,n)

    {

        if(size[color[i]]==1) puts("Safe");

        else puts("Unsafe");

    }

}