本文共 1472 字，大约阅读时间需要 4 分钟。
题面:
本题建图时:夫妻之间:女孩指向男孩情人之间:男孩指向女孩然后Tarjan求强连通分量，对于一对夫妻，如果两人在同一个强连通分量里，那么这对婚姻就是不安全的，反之，则是安全的。 Code:# include # include # include using namespace std;const int N=8010;const int M=20010;int m,n;string c1,c2;map a;struct Edge{ int to,Next;}edge[(M<<1)+N];int head[N],cnt=1,is[(M<<1)+N];int T=0,low[N],dfn[N],s[N],tot=0,ha[N],in[N],n0=0;void add(int u,int v){ edge[++cnt].Next=head[u]; edge[cnt].to=v; head[u]=cnt;}void tarjan(int now){ dfn[now]=low[now]=++T; in[now]=1; s[++tot]=now; for(int i=head[now];i;i=edge[i].Next) { int v=edge[i].to; if(!dfn[v]) { tarjan(v); low[now]=min(low[now],low[v]); } else if(in[v]) low[now]=min(low[now],dfn[v]); } if(dfn[now]==low[now]) { n0++;int k; do { k=s[tot]; tot--; ha[k]=n0; in[k]=0; }while(k!=now); }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>c1>>c2; a[c1]=i; a[c2]=n+i; add(i,n+i); } scanf("%d",&m); for(int i=1;i<=m;i++) { cin>>c1>>c2; add(a[c2],a[c1]); } for(int i=1;i<=n<<1;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) if(ha[i]==ha[i+n]) printf("Unsafe\n"); else printf("Safe\n"); return 0;}
转载于:https://www.cnblogs.com/ukcxrtjr/p/11195444.html