QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#480951#906. 强连通分量james1BadCreeper#WA 4ms32876kbC++17994b2024-07-16 19:48:342024-07-16 19:48:34

Judging History

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

  • [2024-07-16 19:48:34]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:32876kb
  • [2024-07-16 19:48:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5; 

int n, m; 
vector<int> G[N]; 
int dfn[N], low[N], ins[N], st[N], tot, cnt, num; 
vector<int> scc[N]; 

void tarjan(int x) {
    dfn[x] = low[x] = ++num; ins[st[++tot] = x] = 1; 
    for (int y : G[x])
        if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]); 
        else if (ins[y]) low[x] = min(low[x], dfn[y]); 
    if (dfn[x] == low[x]) {
        int y; ++cnt; 
        do scc[cnt].emplace_back(y = st[tot--]), ins[y] = 0; while (x != y); 
    }
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    while (m--) {
        int u, v; cin >> u >> v; 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    }
    for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i); 
    cout << cnt << "\n"; 
    for (int i = 1; i <= cnt; ++i) {
        cout << scc[i].size() << " "; 
        for (int u : scc[i]) cout << u << " "; 
        cout << "\n"; 
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 32876kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

3
4 5 2 4 1 
2 0 3 
1 6 

result:

wrong answer Integer 6 violates the range [0, 5]