Description

我国的离婚率连续 7 年上升, 今年的头两季, 平均每天有近 5000 对夫妇离婚, 大城市的 离婚率上升最快, 有研究婚姻问题的专家认为, 是与简化离婚手续有关. 25 岁的姗姗和男友谈恋爱半年就结婚, 结婚不到两个月就离婚, 是典型的 “闪婚闪离” 例子, 而离婚的 导火线是两个人争玩电脑游戏, 丈夫一气之下, 把电脑炸烂. 有社会工作者就表示, 80 后求助个案越来越多, 有些是与父母过多干预有关. 而根据民政部的统计, 中国离婚 五大城市首位是北京, 其次是上海、深圳, 广州和厦门, 那么到底是什么原因导致我国成为离婚大国呢? 有专家分析说, 中国经济急速发展, 加上女性越来越来越独立, 另外, 近年来简化离婚手续是其中一大原因.----以上内容摘自第一视频门户

现代生活给人们施加的压力越来越大, 离婚率的不断升高已成为现代社会的一大问题. 而其中有许许多多的个案是由婚姻中的 “不安定因素” 引起的. 妻子与丈夫吵架后, 心如绞痛, 于是寻求前男友的安慰, 进而夫妻矛盾激化, 最终以离婚收场, 类似上述的案例数不胜数. 我们已知 \(n\) 对夫妻的婚姻状况, 称第 \(i\) 对夫妻的男方为 \(B_i\), 女方为 \(G_i\). 若某男 \(B_i\) 与某女 \(G_j\) 曾经交往过 (无论是大学, 高中, 亦或是幼儿园阶段,\(i \neq j\)) , 则当某方与其配偶 (即 \(B_i\) 与 \(G_i\) 或 \(B_j\) 与 \(G_j\)) 感情出现问题时, 他们有私奔的可能性. 不妨设 \(B_i\) 和其配偶 \(G_i\) 感情不和, 于是 \(B_i\) 和 \(G_j\) 旧情复燃, 进而 \(B_j\) 因被戴绿帽而感到不爽, 联系上了他的初恋情人 \(G_k\). ...... 一串串的离婚 事件像多米诺骨牌一般接踵而至. 若在 \(B_i\) 和 \(G_i\) 离婚的前提下, 这 \(2n\) 个人最终 依然能够结合成 \(n\) 对情侣, 那么我们称婚姻 \(i\) 为不安全的, 否则婚姻 \(i\) 就是安全的. 给定所需信息, 你的任务是判断每对婚姻是否安全.

Input

第一行为一个正整数 \(n\), 表示夫妻的对数;

以下 \(n\) 行, 每行包含两个字符串, 表示这 \(n\) 对夫妻的姓名 (先女后男), 由一个空格隔开;

第 \(n+2\) 行包含一个正整数 \(m\), 表示曾经相互喜欢过的情侣对数;

以下 \(m\) 行, 每行包含两个字符串, 表示这 \(m\) 对相互喜欢过的情侣姓名 (先女后男), 由一个空格隔开.

Output

输出文件共包含 \(n\) 行, 第 \(i\) 行为 Safe (如果婚姻 \(i\) 是安全的) 或 Unsafe (如果婚姻 \(i\) 是不安全的).

Sample Input

2
Melanie Ashley
Scarlett Charles
1
Scarlett Ashley

Sample Output

Safe
Safe

Data Range

对于 100% 的数据, 所有姓名字符串中只包含英文大小写字母, 大小写敏感, 长度不大于 \(8\), 保证每对关系只在输入文件中出现一次, 输入文件的最后 \(m\) 行不会出现未在之前出现过的姓名, 这 \(2n\) 个人的姓名各不相同,\(1 \leq n \leq 4000, 0 \leq m \leq 20000\).

Explanation

首先先用哈希表把所有字符串都变成数字......

然后考虑这样的一个强连通分量...... 如果两个情侣是不稳定的那么他们一定在一个强连通分量里, 然后这道题就做出来了......

吐槽: 为什么把数组大小改成 12 就不会 RE 然后 64 就会 RE...... ; 还有为什么写对拍的时候还想了一个事情就是会把字符串长度搞错调了好久 QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;
typedef long long lli;
typedef unsigned long long ull;
const int maxn = 10010, maxm = 50100;

class StronglyConnectedComponents
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    edge *edges[maxn], epool[maxm];
    int n, ecnt;
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    int dfn[maxn], low[maxn], instk[maxn], belong[maxn];
    stack<int> stk;
    int dcnt, bcnt;
    void dfs(int p)
    {
        dfn[p] = low[p] = ++dcnt;
        stk.push(p);
        instk[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next) {
            int q = ep->v;
            if (!dfn[q]) {
                dfs(q);
                low[p] = min(low[p], low[q]);
            } else if (instk[q]) {
                low[p] = min(low[p], dfn[q]);
            }
        }
        if (dfn[p] == low[p]) {
            bcnt += 1;
            int q = 0;
            do {
                q = stk.top();
                stk.pop();
                instk[q] = false;
                belong[q] = bcnt;
            } while (q != p);
        }
        return ;
    }
} graph;

inline ull hash(char str[])
{
    ull sum = 0; int l = strlen(str);
    for (int i = 0; i < l; i++)
        sum = sum * 37 + str[i] - '0';
    return sum;
}

struct hobj {
    char s[12]; int next;
} hsh[maxn];
int hh[100009], hcnt;
char str[12];
int get_key(void)
{
    int key = hash(str) % 100009;
    for (int k = hh[key]; k; k = hsh[k].next) {
        if (!strcmp(hsh[k].s, str))
            return k;
    }
    memmove(hsh[++hcnt].s, str, sizeof str);
    hsh[hcnt].next = hh[key];
    hh[key] = hcnt;
    return hcnt;
}

int n, m;
int edge[maxn][2];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int t1 = 0, t2 = 0;
        memset(str, 0, sizeof(str));
        scanf("%s", str); t1 = get_key();
        memset(str, 0, sizeof(str));
        scanf("%s", str); t2 = get_key();
        edge[i][0] = t1; edge[i][1] = t2;
        graph.add_edge(t1, t2);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int t1 = 0, t2 = 0;
        memset(str, 0, sizeof(str));
        scanf("%s", str); t1 = get_key();
        memset(str, 0, sizeof(str));
        scanf("%s", str); t2 = get_key();
        graph.add_edge(t2, t1);
    }
    // Searching.
    for (int i = 1; i <= n; i++)
        if (!graph.belong[edge[i][0]])
            graph.dfs(edge[i][0]);
    // Results
    for (int i = 1; i <= n; i++) {
        if (graph.belong[edge[i][0]] == graph.belong[edge[i][1]])
            printf("Unsafe\n");
        else
            printf("Safe\n");
    }
    return 0;
}