P8435qiutiao
  • 板块学术版
  • 楼主Sukilin
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/13 15:03
  • 上次更新2024/12/13 20:35:53
查看原帖
P8435qiutiao
959201
Sukilin楼主2024/12/13 15:03

最后两个点 TLE。求教是单纯常数太大还是出了本质问题

#include <iostream>
#include <cstdio>
#include <vector>
const int N = 5e5 + 7, M = 2e6 + 7;
int n, m;
int cnt, head[N], nex[N << 1], to[N << 1];
inline void add(int u, int v) {
    nex[++cnt] = head[u];
    to[cnt] = v;
    head[u] = cnt;
}
int i;
int dfn[N], low[N];
int st[N], tp;
std::vector <int> bcc[N];
int bcccnt;
void dfs(int u, int f) {
    int ch = 0;
    dfn[u] = low[u] = ++i;
    st[++tp] = u;
    for(int p = head[u]; p; p = nex[p]) {
        int v = to[p];
        if(!dfn[v]) {
            ++ch;
            dfs(v, u);
            low[u] = std::min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                ++bcccnt;
                int temp;
                do {
                    temp = st[tp--];
                    bcc[bcccnt].push_back(temp);
                } while(temp != v);
                bcc[bcccnt].push_back(u);
            }
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
    if(ch == 0 && f == 0) bcc[++bcccnt].push_back(u);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m;
    for(int p = 1; p <= m; p++) {
        int u, v;
        std::cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for(int v = 1; v <= n; v++)
        if(!dfn[v]) dfs(v, 0);
    std::cout << bcccnt << '\n';
    for(int i = 1; i <= bcccnt; i++) {
        int temp = 0;
        for(auto x : bcc[i]) ++temp;
        std::cout << temp << ' ';
        for(auto x : bcc[i]) std::cout << x << ' ';
        std::cout << '\n';
    }
}
2024/12/13 15:03
加载中...