QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#411619 | #906. 强连通分量 | iee | WA | 0ms | 3576kb | C++17 | 1.1kb | 2024-05-15 16:42:21 | 2024-05-15 16:42:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> e(n), g(n);
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
e[u].push_back(v);
g[v].push_back(u);
}
vector<int> ord, vis(n);
function<void(int)> dfs = [&](int u) {
if (vis[u]) return;
vis[u] = 1;
for (int v : e[u]) {
dfs(v);
}
ord.push_back(u);
};
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i);
}
}
reverse(ord.begin(), ord.end());
vis.assign(n, 0);
vector<int> col(n);
vector<vector<int>> nodes(n);
int rt, tot = 0;
function<void(int)> dfs1 = [&](int u) {
if (vis[u]) return;
vis[u] = 1;
col[u] = rt;
nodes[rt].push_back(u);
for (int v : g[u]) {
dfs1(v);
}
};
for (int i : ord) {
if (!vis[i]) rt = i, dfs1(i), tot++;
}
cout << tot << "\n";
vector<int> out(n);
for (int i = 0; i < n; i++) {
if (out[col[i]]) continue;
out[col[i]] = 1;
sort(nodes[col[i]].begin(), nodes[col[i]].end());
cout << nodes[col[i]].size();
for (int x : nodes[col[i]]) {
cout << " " << x;
}
cout << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3576kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 0 3 2 1 4 1 2 1 5
result:
wrong answer 5 is later than 2, but there is an edge (5, 2)