补全：十万点大环的分量

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

一个十万个点的大环 0→1→…→99999→0。第一遍已经用手写栈写好了。补全第二遍（在反图 rg 上收点，同样用手写栈），输出分量个数。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 补全：手写栈的出栈时机补全：估一估能递归多少层 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;

// 一个十万个点的大环：0→1→…→n-1→0，用手写栈做 Kosaraju 的第一遍
int main() {
    const int n = 100000;
    vector<vector<int>> g(n), rg(n);
    for (int i = 0; i < n; i++) {
        g[i].push_back((i + 1) % n);
        rg[(i + 1) % n].push_back(i);
    }
    vector<bool> seen(n, false);
    vector<int> order;
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        vector<pair<int, int>> st = {{s, 0}};
        seen[s] = true;
        while (!st.empty()) {
            int u = st.back().first;
            int i = st.back().second;
            if (i < (int)g[u].size()) {
                st.back().second++;
                int v = g[u][i];
                if (!seen[v]) {
                    seen[v] = true;
                    st.push_back({v, 0});
                }
            } else {
                order.push_back(u);
                st.pop_back();
            }
        }
    }
    vector<bool> seen2(n, false);
    int comps = 0;
    for (int k = n - 1; k >= 0; k--) {
        int s = order[k];
        if (seen2[s]) continue;
        comps++;
        vector<int> st = {s};
        seen2[s] = true;
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            // TODO: 在反图 rg 上把 u 的邻居里没见过的记进 seen2、压进 st
        }
    }
    cout << comps << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

补全：十万点大环的分量

更多题目

全部评论