lgP1407[国家集训队]稳定婚姻

发表于 | 分类于 ， ， | 阅读数 次

链接:lgP1407[国家集训队]稳定婚姻

题解

  • 尝试将所有丈夫和夫妻连起来，表示他们之间存在过关系，那么显然无论是之前还是现在，他们总有关系，所以这两种情况是一样的
  • 那么怎么判断是否安全呢。
  • 由于已经将所有存在过关系的丈夫和夫妻连起来了，那么显然如果如果丈夫和夫妻在一个环里，那么不安全
  • 注意连接的时候一定要是男->女->男->女这样链接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e6;
struct node{
    int v,nxt;
    inline void init(int a,int b){v=a;nxt=b;}
}e[N];
string a,b;
map<string,int> id;
int n,m,bl[N],head[N],cnt,in[N],dfn[N],low[N],tot,stck[N],idx;

inline void adde(int x,int y){e[cnt].init(y,head[x]);head[x]=cnt++;}

void tarjan(int u){
    in[u]=1;
    low[u]=dfn[u]=++tot;
    stck[++idx]=u;
    for(int i=head[u],v;i!=-1;i=e[i].nxt){
        if(!dfn[v=e[i].v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cnt++;
        do{
            bl[stck[idx--]]=cnt;
            in[stck[idx+1]]=0;
        }while(stck[idx+1]!=u);
    }
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    rep(i,1,n){cin>>a>>b;id[a]=i;id[b]=i+n;adde(i,i+n);}
    scanf("%d",&m);
    rep(i,1,m){cin>>a>>b;adde(id[b],id[a]);}
    cnt=0;
    rep(i,1,2*n)if(!dfn[i])tarjan(i);
    rep(i,1,n)if(bl[i]==bl[i+n])puts("Unsafe");else puts("Safe");
    return 0;
}