codeforces 1239D-Catowice City（tarjan缩点）

codeforces

洛谷

$difficult：2400$

---

难以想到的 $tarjan$ 缩点

考虑朴素做法时可以发现：若存在一条 $i->j(i\ne j)$ 的有向边（默认为 $i$ 人和 $j$ 猫），则可选择的方案有：

1. $i，j$ 同时选人
2. $i，j$ 同时选猫
3. $i$ 选猫，$j$ 选人

在该基础上，如果还存在一条 $j->i$ 的有向边，此时 $i、j$ 构成强联通分量，则可选方案仅剩：全选人或全选猫。特别的，编号相同的人和猫也能被看作强联通分量，由此进行 $tarjan$ 缩点。

由于同一强联通分量内只能同时选人或同时选猫，则强联通块数 $=1$ 时无解。

在其它情况下，由于方案 $3$ 的限制，考虑让没有出度的强联通分量全选人，其它全选猫。

$tarjan$ 缩点的特殊性已保证最后缩到点 $1$ 的即为没有出度的强联通分量。

参考代码

#include 
#define int long long
#define PII pair<int, int>
using namespace std;

const int N = 1e6 + 10;
vector<int> h[N];
bool vis[N], in[N];
int dfn[N], low[N], suo[N], num[N];
stack<int> st;
int tmp = 0, cnt = 0, x = 0;
vector<PII> p;
vector<int> ans[N];
map<PII, int> mp;

void tarjan(int u) {
    dfn[u] = low[u] = ++x;
    vis[u] = in[u] = true;
    st.push(u);

    for (auto v : h[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in[v])
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
        cnt++;
        do {
            tmp = st.top();
            st.pop();
            in[tmp] = false;
            suo[tmp] = cnt;
            ans[cnt].push_back(tmp);  //缩到cnt中的点集
        } while (u != tmp);
    }
}
int n, m;

void init() {
    for (int i = 1; i <= n; i++) {
        h[i].clear();
        dfn[i] = low[i] = suo[i] = num[i] = in[i] = vis[i] = 0;
        ans[i].clear();
    }
    tmp = 0, cnt = 0, x = 0;
    p.clear(), mp.clear();
}

void solve() {
    cin >> n >> m;
    init();
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (u == v)
            continue;
        p.push_back({u, v});
        h[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            tarjan(i);
    }

    if (cnt <= 1) {  //只选人
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
    cout << ans[1].size() << " " << n - ans[1].size() << endl;
    for (auto j : ans[1])
        cout << j << " ";
    cout << endl;
    for (int i = 2; i <= cnt; i++) {
        for (auto j : ans[i])
            cout << j << " ";
    }
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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