社区讨论
蒟蒻刚学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 条回复,欢迎继续交流。
正在加载回复...