P1407 稳定婚姻

た入场券 2021-11-22 08:54 222阅读 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 条评论，222人围观）

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

相关阅读

相关婚姻的本质

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

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

相关婚姻家庭法重点复习提纲

婚姻家庭与继承法复习提纲一、婚姻：婚姻是男女双方以确立夫妻关系为目的，以夫妻的权利义务作为内容的合法结合家庭：家庭是共同生活的，其成员间互享法定权利、互负法律义务的亲

﹏ヽ暗。殇╰゛Y/ 2024年04月01日 19:01/ 0 赞/ 76 阅读

相关婚姻家庭法简答题及答案

婚姻家庭法简答题及答案 1．简述亲权的法律特征。答：亲权是基于父母子女之间的身份权而产生的父母对未成年子女的权利和义务的统一。它具有以下法律特征：（1）亲权是基本的身

朱雀/ 2024年04月01日 19:01/ 0 赞/ 77 阅读

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

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

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

相关爱情和婚姻

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

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

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

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

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

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

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

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

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

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

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

相关 1407: 中序遍历二叉树

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

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

相关 P1407 稳定婚姻

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

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