QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#482115#906. 强连通分量5k_sync_closerWA 1ms8012kbC++201.0kb2024-07-17 17:21:412024-07-17 17:21:41

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 17:21:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8012kb
  • [2024-07-17 17:21:41]
  • 提交

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;
}

详细

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)