「洛谷 P1407」稳定婚姻 - 强连通分量

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

我们已知 \(n\) 对夫妻的婚姻状况，称第 \(i\) 对夫妻的男方为 \(B_i\)，女方为 \(G_i\)。若某男 \(B_i\) 与某女 \(G_j\) 曾经交往过（无论是大学，高中，亦或是幼儿园阶段，\(i \le 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\) 就是安全的。

给定所需信息，你的任务是判断每对婚姻是否安全。

解题思路

显然这道题考得是图的连通性。

由于若一人感情不和，随之不和的是异性，我们可以在异性之间连有向边。

于是我们可以考虑用以下方式建图：

  • 对于夫妻，我们连一条 \(G_i \rightarrow B_i\) 的有向边；

  • 对于情侣，我们连一条 \(B_i \rightarrow G_j\) 的有向边。

接下来跑一边 Tarjan 求强连通分量。若 \(G_i\) 和 \(B_i\) 在同一个强连通分量中，则他们的婚姻是不安全的。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <iostream>
#include <stack>
#include <map>

const int MAXN = 4000;

struct Node {
    struct Edge *edges;
    int dfn, low;
    bool visited;
    struct Connected *connected;
} N[2 * MAXN];

struct Edge {
    Node *from, *to;
    Edge *next;

    Edge(Node *from, Node *to) : from(from), to(to), next(from->edges) {}
};

struct Connected {
    int size;
} connecteds[2 * MAXN];


int n, m;
std::string girl[MAXN], boy[MAXN];
std::map<std::string, int> mp;

inline void addEdge(int from, int to) {
    N[from].edges = new Edge(&N[from], &N[to]);
}

void tarjan(Node *x) {
    static int num = 0, counts = 0;
    static std::stack<Node *> stk;
    x->dfn = x->low = ++num;
    stk.push(x);
    x->visited = true;

    for (Edge *edges = x->edges; edges; edges = edges->next) {
        if (!edges->to->dfn) {
            tarjan(edges->to);
            x->low = std::min(x->low, edges->to->low);
        } else if (edges->to->visited) {
            x->low = std::min(x->low, edges->to->dfn);
        }
    }

    if (x->dfn == x->low) {
        counts++;
        Node *y;
        do {
            y = stk.top();
            stk.pop();
            y->visited = false;
            y->connected = &connecteds[counts];
            connecteds[counts].size++;
        } while (x != y);
    }
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        std::cin >> girl[i] >> boy[i];
        mp[girl[i]] = 2 * i;
        mp[boy[i]] = 2 * i + 1;
        addEdge(mp[girl[i]], mp[boy[i]]);
    }

    scanf("%d", &m);

    for (int i = 0; i < m; i++) {
        std::string g, b;
        std::cin >> g >> b;
        addEdge(mp[b], mp[g]);
    }

    for (int i = 0; i < 2 * n; i++) {
        if (!N[i].dfn) {
            tarjan(&N[i]);
        }
    }

    for (int i = 0; i < n; i++) {
        if (N[mp[girl[i]]].connected == N[mp[boy[i]]].connected) puts("Unsafe");
        else puts("Safe");
    }

    return 0;
}