关键词：
这道题一开始可能以为是二分图匹配……？不过后来发现和二分图没啥大关系。
简单分析之后发现，把夫妻之间连边（男性向女性连边），之后再将每对曾经是情侣的人连边（女性向男性连边），当然以上的方向可以反过来不过两次连接方向必须相反。这样的话如果婚姻是危险的那么这些就是在一个强连通分量里面的。换句话说，如果一个强连通分量中有多于1个点，那么就说明这个婚姻并不稳定（夫妻之间连单向边，所以如果婚姻稳定的话夫妻不会出现在一个强连通分量之中）
这样的话就比较好办了，直接如上述方法见图之后跑tarjan求出强连通分量，记录下来每个强连通分量之中的点数即可。还有这道题需要使用map映射一下。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #include<map> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(‘ ‘) using namespace std; typedef long long ll; const int M = 50005; int read() int ans = 0,op = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) if(ch == ‘-‘) op = -1; ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘) ans *= 10; ans += ch - ‘0‘; ch = getchar(); return ans * op; struct edge int next,to; e[M<<2]; int n,m,cnt,ecnt,cur,low[M],dfn[M],stack[M],top,curr,vis[M],belong[M],head[M]; bool in[M]; string f[M],a,b; map <string,int> p; void add(int x,int y) e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; void tarjan(int x) low[x] = dfn[x] = ++cur; in[x] = 1,stack[++top] = x; for(int i = head[x];i;i = e[i].next) if(!dfn[e[i].to]) tarjan(e[i].to),low[x] = min(low[x],low[e[i].to]); else if(in[e[i].to]) low[x] = min(low[x],dfn[e[i].to]); if(dfn[x] == low[x]) int p; curr++; while(p = stack[top--]) in[p] = 0,belong[p] = curr; if(x == p) break; void solve() rep(i,1,cnt) if(!dfn[i]) tarjan(i); rep(i,1,cnt) vis[belong[i]]++; for(int i = 1;i <= n<<1;i += 2) if(vis[belong[p[f[i]]]] > 1) printf("Unsafe "); else printf("Safe "); int main() n = read(); rep(i,1,n) cin >> a >> b; f[++cnt] = a,p[a] = cnt; f[++cnt] = b,p[b] = cnt; add(cnt-1,cnt); m = read(); rep(i,1,m) cin >> a >> b,add(p[b],p[a]); solve(); return 0;
luogup1407[国家集训队]稳定婚姻(代码片段)
...$tarjan$，如果对于一对夫妻在强连通分量里，那么就是不稳定的，因为他们可以绕一圈。 #include<iostream>#include<cstdio>#include<cstring>#include<string>#include<map& 查看详情
bzoj2140:稳定婚姻图论-tarjan
【bzoj2140】:稳定婚姻哎。。都是模板题。。一眼看过去哇二分图哎然后发现好像并不能匈牙利算法自己xjb画两张图，发现二分图左向右连配偶的边，然后右向左连交往过的边然后如果BiGi在同一个强连通分量里面就一定可以在BiGi... 查看详情
模板：稳定婚姻问题(代码片段)
1#include<bits/stdc++.h>2usingnamespacestd;34constintN=234;56intRank[N][N];//i,j第i个人心中,第j排名是谁7intM[N][N];//i,jj在i心中的排名8intboy[N],girl[N],Next[N];9intn,t;1011voidsolve()12memset(boy,0,sizeof(boy 查看详情
稳定婚姻模型(代码片段)
原文地址：https://blog.csdn.net/qq_33913037/article/details/71328099 假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中... 查看详情
稳定婚姻匹配问题(代码片段)
假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中的排名(1)，你应该怎样为他们牵线配对呢？ ... 查看详情
uoj.41.[清华集训2014]矩阵变换(稳定婚姻)(代码片段)
题目链接稳定婚姻问题：有n个男生n个女生，每个男/女生对每个女/男生有一个不同的喜爱程度。给每个人选择配偶。若不存在x,y未匹配，且x喜欢y胜过喜欢x当前的配偶，y喜欢x也胜过y当前的配偶的完备匹配，则称这是一个稳定... 查看详情
使用gale-shapley算法解决稳定婚姻问题(代码片段)
Gale-Shapley算法又叫做延迟认可算法，它可以解决这么一个问题一共有N位男士和N位女士每位男士对每位女士都有一个好感度，让他们结合成为N对夫妻，要求男士优先表白，最后问结合情况第一轮，每个男人都选择自己名单上排在... 查看详情
bzoj2140稳定婚姻（强联通分量判环）bzoj修复工程(代码片段)
整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划题目链接https://hydro.ac/d/bzoj/p/2140是hydro的BZOJ修复工程！（我也去领了一点题慢慢修着玩，这题就是我修... 查看详情
bzoj2140稳定婚姻（强联通分量判环）bzoj修复工程(代码片段)
整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划题目链接https://hydro.ac/d/bzoj/p/2140是hydro的BZOJ修复工程！（我也去领了一点题慢慢修着玩，这题就是我修... 查看详情
hdu1522marriageisstable稳定婚姻匹配(模板题)(代码片段)
...欢程度越高的两个异性越容易配对，现在求出它们之间的稳定匹配。解题分析：稳定婚姻问题的模板题，需要用到Gale_Shapley算法，GS算法讲解 >>>这个算法还是很直观的。1#include<iostream>2#include<cstring>3#include<st... 查看详情
marriageisstablehdu1522稳定婚姻问题(代码片段)
...理的匹配要打印名字的话必须有一个名字数组英文名用map稳定婚姻问题：每次循环遍历所有的男的每个男的对目前未被拒绝的并且优先级最高的进行预匹配 如果1女的没有伴侣2女的对该男的好感度比女的伴侣的好感度更高&nbs... 查看详情
euphoria(代码片段)
...会了Tarjan...www(千辛万苦抱头哭泣嘤嘤嘤P1407[国家集训队]稳定婚姻我们已知n对夫妻的婚姻状况，称第i对夫妻的男方为Bi，女方为Gi。若某男Bi与某女Gj曾经交往过（无论是大学，高中，亦或是幼儿园阶段，i≠j），则当某方与其配... 查看详情
tarjan求lca(代码片段)
...等等今天在这里给大家讲一下tarjan算法！tarjan求LCA是一种稳定高速的算法时间复杂度能做到预处理O(n+m)，查询O(1)它的主要思想是dfs和并查集1.输入数据，找出根节点(或输入的)并将图存起来2.输入需要查找的每一对点(两个点)，也... 查看详情
题解p1407(代码片段)
...破的关系数和新建立的关系数相同)，所以这个婚姻就不稳定。所以建完图后可以跑Tarjan，如果一对夫妇在同一个SCC中，这个婚姻就不稳定。#include<cstdio>#include<iostream>#include<map>#include<string>usingnamespacestd;map<stri... 查看详情
poj3487[稳定婚姻]
TheStableMarriageProblemTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 2974 Accepted: 1267DescriptionThestablemarriageproblemconsistsofmatchingmembersoftwodifferentsetsacco 查看详情
稳定婚姻匹配问题
...安排这N个男的、N个女的结婚，要求两个人的婚姻应该是稳定的。 何为稳定？ 有两对夫妻M1F2，M2F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的， ... 查看详情
稳定婚姻问题(stablemarriageproblem)
转自http://www.cnblogs.com/drizzlecrj/archive/2008/09/12/1290176.html稳定婚姻是组合数学里面的一个问题。问题大概是这样：有一个社团里有n个女生和n个男生，每位女生按照她的偏爱程度将男生排序，同时每位男生也按照自己的偏爱程度将... 查看详情
hdu1914稳定婚姻匹配
TheStableMarriageProblemTimeLimit:5000/1000MS(Java/Others) MemoryLimit:65535/32768K(Java/Others)TotalSubmission(s):758 AcceptedSubmission(s):389ProblemDes 查看详情