题解 P1407

建图方式：旧关系女人连男人，现关系男人连女人(当然，反过来也可以)

原因可以这样考虑：

如果一个男的把女的绿了，那么这个女人就会去找一个她曾经交往过的男人，也就是在这种情况下，某种“影响”会顺着旧关系从女人传到男人，而此时这个男人又会顺着原关系把这种“影响”传给另一个女人；如果这种“影响”传回了那个男人，就说明那个男人也成功配对，并且这种“影响”的传递路径上正向边和反向边的个数相同(即被打破的关系数和新建立的关系数相同)，所以这个婚姻就不稳定。

所以建完图后可以跑Tarjan，如果一对夫妇在同一个SCC中，这个婚姻就不稳定。

#include 
#include 
#include 
#include 
using namespace std;
map M;
const int MAXN = 200000;
int cnt;
int head[MAXN], nxt[MAXN], to[MAXN];
int tot;
void ins(int u, int v)
{
	nxt[++cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
}
int dfn[MAXN], low[MAXN], clo[MAXN];
int vis[MAXN], sta[MAXN], top;
void tarjan(int u)
{
	sta[++top] = u;
	dfn[u] = low[u] = ++tot;
	vis[u] = 1;
	for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	if (low[u] == dfn[u])
	{
		clo[u] = u;
		vis[u] = 0;
		int y;
		while ((y = sta[top--]) != u)
			clo[y] = u, vis[y] = 0;
	}
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m;
	int u, v;
	string girl, boy;
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> girl;
		u = M[girl] = ++tot;
		cin >> boy;
		v = M[boy] = ++tot;
		ins(u, v);
	}
	cin >> m;
	tot = 0;
	for (int i = 1; i <= m; ++i)
	{
		cin >> girl;
		cin >> boy;
		v = M[girl];
		u = M[boy];
		ins(u, v);
	}
	for (int i = 1; i <= (n << 1); ++i)
		if (!dfn[i])
			tarjan(i);
	for (int i = 1; i <= n; ++i)
		if (clo[i << 1] == clo[(i << 1) - 1])
			cout << "Unsafe\n";
		else
			cout << "Safe\n";
	return 0;
}
Tarjan洛谷

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

LCA/在线(倍增)离线(Tarjan)

洛谷 P2440 木材加工

关于tarjan算法的一些整理

洛谷 P2404 自然数的拆分问题

洛谷T198835

洛谷 P3817 小A的糖果

洛谷 P1309 瑞士轮 归并排序

洛谷 P2279 [HNOI2003]消防局的设立 贪心

洛谷 P1449 后缀表达式

洛谷 P2791 - 幼儿园篮球题（第二类斯特林数）

『笔记』tarjan 双连通分量，强连通分量

标签