QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482115 | #906. 强连通分量 | 5k_sync_closer | WA | 1ms | 8012kb | C++20 | 1.0kb | 2024-07-17 17:21:41 | 2024-07-17 17:21:41 |
Judging History
answer
#include <cstdio>
#include <vector>
using namespace std;
struct E
{
int v, t;
} e[100050];
vector<int> v[100050];
bool b[100050];
int n, m, c, _, C, L, d[100050], l[100050], h[100050], S[100050];
void A(int u, int v) { e[++c] = {v, h[u]}, h[u] = c; }
void T(int u)
{
d[u] = l[u] = ++_, b[S[++L] = u] = 1;
for (int i = h[u], v; i; i = e[i].t)
if (!d[v = e[i].v])
T(v), l[u] = min(l[u], l[v]);
else if (b[v])
l[u] = min(l[u], d[v]);
if (d[u] == l[u])
{
++C;
int z = -1;
while (z != u)
b[z = S[L--]] = 0, v[C].push_back(z);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0, u, v; i < m; ++i)
scanf("%d%d", &u, &v), A(u, v);
for (int i = 0; i < n; ++i)
if (!d[i])
T(i);
printf("%d\n", C);
for (int i = 1; i <= C; ++i)
{
printf("%d ", v[i].size());
for (auto j : v[i])
printf("%d ", j);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 8012kb
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)