【信奥做题日记】初中生太难了！怒刷1道【强连通分量】题目

#include <bits/stdc++.h>

using  namespace  std;

const  int maxn = 1e4 + 5;
const  int maxm = 2e5 + 5;
typedef  long  long ll;
int dfn[maxn], low[maxn], color[maxn], t = 1, n, m, c = 0;
bool vis[maxn];

struct edge {
    int from, to, next;
} g[maxm];
struct Couple {
    string u, v;
} couple[maxn];
int head[maxn];
int k = 0;

void add(int u, int v) {
    g[++k].to = v;
    g[k].from = u;
    g[k].next = head[u];
    head[u] = k;
}

stack<int> st;
void tarjan(int x) {
    st.push(x);
    vis[x] = true;
    dfn[x] = t;
    low[x] = t;
    ++t;
    for (int i = head[x]; i; i = g[i].next) {
        int v = g[i].to;
        if (dfn[v] == 0) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if (vis[v]) {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if (dfn[x] == low[x]) {
        ++c;
        while (!st.empty()) {
            int u = st.top();
            vis[u] = false;
            st.pop();
            color[u] = c;
            if (x == u) {
                break;
            }
        }

    }
}

void best_coder() {
    unordered_map<string, int> name;
    cin >> n;
    int a = 1;
    for (int i = 0; i < n; ++i) {
        cin >> couple[i].u >> couple[i].v;
        name[couple[i].u] = a++;
        name[couple[i].v] = a++;
        add(a - 2, a - 1);
    }
    cin >> m;
    for (int i = 0; i < m; ++i) {
        string u, v;
        cin >> u >> v;
        add(name[v], name[u] );
    }
    for (int i = 1; i <= n * 2; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    for (int i = 0; i < n; ++i) {
        int u = name[couple[i].u];
        int v = name[couple[i].v];
        if (color[u] == color[v]) {
            cout << "Unsafe\n";
        } else {
            cout << "Safe\n";
        }
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}