问题描述
我国的离婚率连续 7 年上升, 今年的头两季, 平均每天有近 5000 对夫妇离婚, 大城市的离婚率上升最快, 有研究婚姻问题的专家认为, 是与简化离婚手续有关. 25 岁的姗姗和男友谈恋爱半年就结婚, 结婚不到两个月就离婚, 是典型的 "闪婚闪离" 例子, 而离婚的导火线是两个人争玩电脑游戏, 丈夫一气之下, 把电脑炸烂. 有社会工作者就表示, 80 后求助个案越来越多, 有些是与父母过多干预有关. 而根据民政部的统计, 中国离婚五大城市首位是北京, 其次是上海, 深圳, 广州和厦门, 那么到底是什么原因导致我国成为离婚大国呢? 有专家分析说, 中国经济急速发展, 加上女性越来越来越独立, 另外, 近年来简化离婚手续是其中一大原因.
? -- 以上内容摘自第一视频门户现代
生活给人们施加的压力越来越大, 离婚率的不断升高已成为现代社会的一大问题. 而其中有许许多多的个案是由婚姻中的 "不安定因素" 引起的. 妻子与丈夫吵架后, 心如绞痛, 于是寻求前男友的安慰, 进而夫妻矛盾激化, 最终以离婚收场, 类似上述的案例数不胜数. 我们已知 n 对夫妻的婚姻状况, 称第 i 对夫妻的男方为 Bi, 女方为 Gi. 若某男 Bi 与某女 Gj 曾经交往过 (无论是大学, 高中, 亦或是幼儿园阶段, i≠j), 则当某方与其配偶(即 Bi 与 Gi 或 Bj 与 Gj) 感情出现问题时, 他们有私奔的可能性. 不妨设 Bi 和其配偶 Gi 感情不和, 于是 Bi 和 Gj 旧情复燃, 进而 Bj 因被戴绿帽而感到不爽, 联系上了他的初恋情人 Gk...... 一串串的离婚事件像多米诺骨牌一般接踵而至. 若在 Bi 和 Gi 离婚的前提下, 这 2n 个人最终依然能够结合成 n 对情侣, 那么我们称婚姻 i 为不安全的, 否则婚姻 i 就是安全的. 给定所需信息, 你的任务是判断每对婚姻是否安全.
输入格式
第一行为一个正整数 n, 表示夫妻的对数;
以下 n 行, 每行包含两个字符串, 表示这 n 对夫妻的姓名(先女后男), 由一个空格隔开;
第 n+2 行包含一个正整数 m, 表示曾经相互喜欢过的情侣对数;
以下 m 行, 每行包含两个字符串, 表示这 m 对相互喜欢过的情侣姓名(先女后男), 由一个空格隔开.
所有姓名字符串中只包含英文大小写字母, 大小写敏感, 长度不大于 8,
保证每对关系只在输入文件中出现一次, 输入文件的最后 m 行不会出现未在之前出现过的姓名,
这 2n 个人的姓名各不相同,
1≤n≤4000,0≤m≤20000.
输出格式
输出文件共包含 n 行, 第 i 行为 "Safe"(如果婚姻 i 是安全的)或 "Unsafe"(如果婚姻 i 是不安全的).
样例输入
[样例输入 1]
- 2
- Melanie Ashley
- Scarlett Charles
- 1
- Scarlett Ashley
[样例输入 2]
- 2
- Melanie Ashley
- Scarlett Charles
- 2
- Scarlett Ashley
- Melanie Charles
样例输出
[样例输出 1]
Safe
Safe
[样例输出 2]
Unsafe
Unsafe
解析
反套路......
把所有男性设成黑点, 女性设成白点, 所有婚姻关系和情侣关系看成边. 那么可以发现以下两点:
如果一对婚姻在一个黑白点交错的环上, 那么这对婚姻是不安全的.
如果一对婚姻在婚姻关系和情侣关系交错的环上, 那么这对婚姻是不安全的.
考虑把所有边定向: 婚姻关系男向女连边, 情侣关系女向男连边. 那么可以发现, 如果一对婚姻的男女方在同一个强连通分量里, 那么这对婚姻是不安全的.
代码
- #include <iostream>
- #include <cstdio>
- #include <map>
- #define N 8002
- #define M 40002
- using namespace std;
- map<string,int> d;
- int head[N],ver[M],nxt[M],l;
- int n,m,i,num,dfn[N],low[N],scc[N],tim,cnt,s[N],top,a[N][2];
- bool in[N];
- int read()
- {
- char c=getchar();
- int w=0;
- while(c<'0'||c>'9') c=getchar();
- while(c<='9'&&c>='0'){
- w=w*10+c-'0';
- c=getchar();
- }
- return w;
- }
- void insert(int x,int y)
- {
- l++;
- ver[l]=y;
- nxt[l]=head[x];
- head[x]=l;
- }
- void Tarjan(int x)
- {
- dfn[x]=low[x]=++tim;
- in[x]=1;
- s[++top]=x;
- for(int i=head[x];i;i=nxt[i]){
- int y=ver[i];
- if(!dfn[y]){
- Tarjan(y);
- low[x]=min(low[x],low[y]);
- }
- else if(in[y]) low[x]=min(low[x],dfn[y]);
- }
- if(low[x]==dfn[x]){
- cnt++;
- while(1){
- int y=s[top--];
- in[y]=0;
- scc[y]=cnt;
- if(x==y) break;
- }
- }
- }
- int main()
- {
- n=read();
- for(i=1;i<=n;i++){
- string s,t;
- cin>>s>>t;
- if(d[s]==0) d[s]=++num;
- if(d[t]==0) d[t]=++num;
- a[i][0]=d[s];a[i][1]=d[t];
- insert(a[i][0],a[i][1]);
- }
- m=read();
- for(i=1;i<=m;i++){
- string s,t;
- cin>>s>>t;
- if(d[s]==0) d[s]=++num;
- if(d[t]==0) d[t]=++num;
- insert(d[t],d[s]);
- }
- for(i=1;i<=num;i++){
- if(!dfn[i]) Tarjan(i);
- }
- for(i=1;i<=n;i++){
- int x=a[i][0],y=a[i][1];
- if(scc[x]==scc[y]) puts("Unsafe");
- else puts("Safe");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3122916.html