QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424680 | #906. 强连通分量 | Adorable | WA | 2ms | 7704kb | C++23 | 1.6kb | 2024-05-29 15:22:49 | 2024-05-29 15:22:54 |
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 = 500100;
stack<int> stk;
vector<int> z[N], scc[N];
int idx, tot, low[N], dfn[N], instk[N], bel[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();
bel[a] = tot, instk[a] = 0;
}
int a = stk.top(); stk.pop();
bel[a] = tot, 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);
}
}
F(i, 0, n - 1) {
scc[bel[i]].pb(i);
}
cout << tot << '\n';
F(i, 1, tot) {
cout << scc[i].size() << ' ';
for (auto &x : scc[i]) {
cout << x << ' ';
}
cout << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7704kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 0 3 1 2 2 1 4 1 5
result:
wrong answer 5 is later than 2, but there is an edge (5, 2)