QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#424669 | #906. 强连通分量 | Adorable | WA | 6ms | 5580kb | C++23 | 1.5kb | 2024-05-29 15:17:51 | 2024-05-29 15:17:52 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;i++)
#define G(i,x,y) for(int i=x;i>=y;i--)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#define inf (7611257611378358090ll/2)
#define inf2 0x3f3f3f3f
using namespace std;
const int mod = 1e9 + 9, N = 5000100;
stack<int> stk;
vector<int> z[N], scc[N];
int idx, tot, low[N], dfn[N], instk[N];
void dfs(int u) {
dfn[u] = low[u] = ++idx;
instk[u] = 1, stk.push(u);
W(z, j, u) {
if (!dfn[j]) {
dfs(j);
low[u] = min(low[u], low[j]);
} else if (instk[j]) {
low[u] = min(low[u], dfn[j]);
}
}
if (dfn[u] == low[u]) {
tot++;
while (stk.top() != u) {
int a = stk.top(); stk.pop();
scc[tot].pb(a), instk[a] = 0;
}
int a = stk.top(); stk.pop();
scc[tot].pb(a), instk[a] = 0;
}
}
auto main() [[O3]] -> signed {
int n, m;
cin >> n >> m;
F(i, 0, m - 1) {
int u, v;
cin >> u >> v;
add(u, v);
}
F(i, 0, n - 1) {
if (!dfn[i]) {
dfs(i);
}
}
cout << tot << '\n';
F(i, 1, tot) {
cout << scc[i].size() << ' ';
for (auto &x : scc[i]) {
cout << x << ' ';
}
cout << '\n';
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 5580kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 3 0 1 2 2 4 1 1 5
result:
wrong answer 5 is later than 2, but there is an edge (5, 2)