QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#480951 | #906. 强连通分量 | james1BadCreeper# | WA | 4ms | 32876kb | C++17 | 994b | 2024-07-16 19:48:34 | 2024-07-16 19:48:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m;
vector<int> G[N];
int dfn[N], low[N], ins[N], st[N], tot, cnt, num;
vector<int> scc[N];
void tarjan(int x) {
dfn[x] = low[x] = ++num; ins[st[++tot] = x] = 1;
for (int y : G[x])
if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
else if (ins[y]) low[x] = min(low[x], dfn[y]);
if (dfn[x] == low[x]) {
int y; ++cnt;
do scc[cnt].emplace_back(y = st[tot--]), ins[y] = 0; while (x != y);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> m;
while (m--) {
int u, v; cin >> u >> v;
G[u].emplace_back(v); G[v].emplace_back(u);
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
cout << cnt << "\n";
for (int i = 1; i <= cnt; ++i) {
cout << scc[i].size() << " ";
for (int u : scc[i]) cout << u << " ";
cout << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 32876kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
3 4 5 2 4 1 2 0 3 1 6
result:
wrong answer Integer 6 violates the range [0, 5]