题解
很好的\(Tarjan\)练习题。
主要讲一下如何建图。
先用\(STL \ map\)把每个人的名字映射成数字。
输入第\(i\)对夫妻时把女性映射成\(i\)，把男性映射成\(i+n\)。
输入相互喜欢过的情侣时将男性向女性连边。
然后\(Tarjan\)判断\(i\)与\(i+n\)是不是在同一个强连通分量里即可。
今天是七夕节诶
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <string>
#define gI gi
#define itn int
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
map <string, int> ap; //map映射
int n, m, ans, sum, low[100003], dfn[100003], num, tot, head[100003], ver[100003], nxt[100003], sy[100003];
int cnt, sta[100003], vis[100003], kok;
inline void add(int u, int v)
{
ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
void Tarjan(int u)//tarjan过程
{
dfn[u] = low[u] = ++num; vis[u] = 1; sta[++cnt] = u;
for (int i = head[u]; i; i = nxt[i])
{
int v = ver[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 (dfn[u] == low[u])
{
int y = -1;
++kok;
do
{
y = sta[cnt];
vis[y] = 0;
sy[y] = kok;
--cnt;
} while (y != u);
}
}
int main()
{
//File("P1407");
n = gi();
for (int i = 1; i <= n; i+=1)
{
string s, ss;
cin >> s;
cin >> ss;
ap[s] = i; ap[ss] = i + n;//映射
add(i, i + n);//连边
}
m = gi();
for (int i = 1; i <= m; i+=1)
{
string s, ss;
cin >> s;
cin >> ss;
add(ap[ss], ap[s]);//连边
}
for (int i = 1; i <= 2 * n; i+=1)
{
if (!dfn[i]) Tarjan(i);
}
for (int i = 1; i <= n; i+=1)
{
if (sy[i] == sy[i + n]) puts("Unsafe");
else puts("Safe");
}
return 0;
}