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

@Pelom  October 24, 2019

题意

数据范围:$1 \le n \le 4000,0 \le m \le 20000$

题解

若成环,则一定是男$\rightarrow$女$\rightarrow$男$\rightarrow \dots$交替,所以建边时两种建边方向应相反,即夫妻关系由男$\rightarrow$女,情侣关系由女$\rightarrow$男
然后跑$\mathrm{Tarjan}$即可

代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<stack>
#include<unordered_map>
using namespace std;
const int N=4000+10;
const int M=20000+10;
int n,m;
string a,b;
int cnt,tot,dep;
int head[N<<1],dfn[N<<1],low[N<<1],clr[N<<1];
stack<int> S;
unordered_map<string,int> um;
struct edge{
    int nxt,to;
} e[(N+M)<<1];
inline void add(int u,int v){
    e[++cnt]=edge{head[u],v};
    head[u]=cnt;
}
void Tarjan(int u){
    dfn[u]=low[u]=++dep;
    S.push(u);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!clr[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        tot++;
        for(int t=0;t!=u;){
            t=S.top();
            S.pop();
            clr[t]=tot;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        um[a]=i;
        um[b]=i+n;
        add(i,i+n);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        add(um[b],um[a]);
    }
    for(int i=1;i<=(n<<1);i++)
        if(!dfn[i])
            Tarjan(i);
    for(int i=1;i<=n;i++)
        if(clr[i]==clr[i+n])
            puts("Unsafe");
        else puts("Safe");
    return 0;
}

添加新评论