P1407

对于数据读入的处理就是用map将字符串映射为一个数值即可。

我们称n对为夫妇， m对为情人， 如果把这n+m对关系都用边相连，我们可以得到很多个环，在环中如果一对夫妇离婚，那么两个人都可以和环中的情人分别再进行配对，所以我们可以用tarjan来判断一对夫妇是否都在同一个环中，如果在那么这对婚姻就不安全，反之则安全。

tarjan找强联通的对象是有向图，我们可以这样处理：在夫妇中女向男连边， 情人中男向女连边，这样能保证图中男女交替相连。

剩下的就是tarjan模板了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 2e5 + 10;
 4 int n, m, t, tot, idx;
 5 int dfn[N], low[N], vis[N], bel[N];
 6 int head[N], to[N << 1], nxt[N << 1];
 7 stack<int> s;
 8 map<string, int> mp;
 9 void add(int a, int b) {
10     nxt[++ tot] = head[a]; head[a] = tot; to[tot] = b;
11 }
12 void tarjan(int x) {
13     dfn[x] = low[x] = ++ t;
14     s.push(x), vis[x] = 1;
15     for (int i = head[x]; i; i = nxt[i]) {
16         int y = to[i];
17         if (!dfn[y]) {
18             tarjan(y);
19             low[x] = min(low[x], low[y]);
20         }
21         else if (vis[y]) 
22             low[x] = min(low[x], dfn[y]);
23     }
24     if (dfn[x] == low[x]) {
25         idx ++;
26         int v;
27         do {
28             v = s.top();
29             s.pop();
30             vis[v] = 0;
31             bel[v] = idx;
32         } while (v != x);
33     }
34 }
35 int main() {
36     ios::sync_with_stdio(false);
37     cin.tie(0), cout.tie(0);
38     cin >> n; string a, b;
39     for (int i = 1; i <= n; i ++) {
40         cin >> a >> b;
41         mp[a] = i, mp[b] = i + n;
42         add(i, i + n);
43     }
44     cin >> m;
45     for (int i = 1; i <= m; i ++) {
46         cin >> a >> b;
47         add(mp[b], mp[a]);
48     }
49     m = n << 1;
50     for (int i = 1; i <= m; i ++)
51         if (!dfn[i]) tarjan(i); 
52     for (int i = 1; i <= n; i ++)
53         if (bel[i] == bel[i + n]) printf("Unsafe\n");
54         else printf("Safe\n");
55     return 0;
56 }