P1407 稳定婚姻

た入场券 2021-11-22 08:54 178阅读 0赞

题面:[https://www.luogu.org/problemnew/show/P1407][https_www.luogu.org_problemnew_show_P1407]

本题建图时: 夫妻之间:女孩指向男孩 情人之间:男孩指向女孩 然后Tarjan求强连通分量，对于一对夫妻，如果两人在同一个强连通分量里，那么这对婚姻就是不安全的，反之，则是安全的。 Code: # include <iostream> # include <cstdio> # include <map> using namespace std; const int N=8010; const int M=20010; int m,n; string c1,c2; map <string,int > 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

[https_www.luogu.org_problemnew_show_P1407]: https://www.luogu.org/problemnew/show/P1407

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关婚姻的本质

吃一经济基础，睡一生理和谐，聊一精神共鸣。这三件事中都没有，基本就可以分开了,不然图什么呢?我这个是在一个软件上看一个离异的老哥发的动态，我思想上比较认可的。所以，婚姻生...

「爱情、让人受尽委屈。」/ 2024年04月22日 15:09/ 0 赞/ 41 阅读

相关 Easy之1407.排名靠前的旅行者

表：Users <table> <thead> <tr> <th>Column Name</th> <th>Type</th> </tr>

妖狐艹你老母/ 2022年10月12日 00:46/ 0 赞/ 143 阅读

相关稳定排序和不稳定排序

这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当然如果你笔试之前已经记住了数据结

拼搏现实的明天。/ 2022年07月17日 03:23/ 0 赞/ 129 阅读

相关爱情和婚姻

有一天，柏拉图问老师苏格拉底什么是爱情？老师就让他先到到麦田里去，摘一棵全麦田里最大最金黄的麦穗来，期间只能摘一次，并且只可向前走，不能回头。　　　　　　柏拉图于是按照老师说

骑猪看日落/ 2022年07月10日 18:24/ 0 赞/ 150 阅读

相关稳定排序和不稳定排序

这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当然如果你笔试之前已经记住了数据

淡淡的烟草味﹌/ 2022年06月18日 09:38/ 0 赞/ 134 阅读

相关稳定排序和不稳定排序

转载自：http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html 这几天笔试了好几次了，连续碰到

野性酷女/ 2022年06月09日 05:10/ 0 赞/ 162 阅读

相关稳定排序和不稳定排序

稳定排序和不稳定排序 1.如何区分？ 2.稳定性意义的探讨 1.如何区分？稳定排序：排序前后两个相等的数相对位置不变，则算法稳定非稳定排序：排

╰+攻爆jí腚メ/ 2022年04月23日 01:28/ 0 赞/ 194 阅读

相关婚姻中关于"容易生气"

其实人在生气的时候是管不住自己的。悲伤、愤怒伤人伤己。所以要注意自己的习惯，平常时候的生活状态。给自己设定一个目标，例如：我在一个星期内没有生气，等做到了，再延

水深无声/ 2022年03月26日 04:53/ 0 赞/ 165 阅读

相关 1407: 中序遍历二叉树

题目描述给定一颗二叉树，要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。输入输入数据分为多组，第一行是测试数据的组数

比眉伴天荒/ 2022年03月22日 10:18/ 0 赞/ 106 阅读

相关 P1407 稳定婚姻

题面:[https://www.luogu.org/problemnew/show/P1407][https_www.luogu.org_problemnew_show_P14

た入场券/ 2021年11月22日 08:54/ 0 赞/ 179 阅读