社区讨论

蒟蒻刚学OI两秒钟,0pts求条

P8435【模板】点双连通分量参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhjkpb0f
此快照首次捕获于
2025/11/04 04:09
4 个月前
此快照最后确认于
2025/11/04 04:09
4 个月前
查看原帖
CPP
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e6 + 5;
int n, m, dfn[N], low[N], stk[N], top, tot, cnt;
vector<int> g[N], ans[N];
char buf[1<<21], *p1 = buf;
inline int read() {
    while (!isdigit(*p1)) ++p1;
    int res = 0;
    while (isdigit(*p1)) res = res * 10 + (*p1++ ^ 48);
    return res;
}
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    for (int v : g[u]) if (v != fa) {
        if (!dfn[v]) {
            tarjan(v, u);
            if (low[v] >= dfn[u]) {
                ans[++cnt].push_back(u);
                do ans[cnt].push_back(stk[top]);
                while (stk[top--] != v);
            }
            low[u] = min(low[u], low[v]);
        } else low[u] = min(low[u], dfn[v]);
    }
}
int main() {
    fread(buf, 1, 1<<21, stdin);
    n = read(), m = read();
    for (int i = 0; i < m; ++i) {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i, -1);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i) {
        printf("%zu ", ans[i].size());
        for (int x : ans[i]) printf("%d ", x);
        putchar('\n');
    }
    return 0;
}
顺便再问一下火车头能否使用

回复

1 条回复,欢迎继续交流。

正在加载回复...