QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618891#906. 强连通分量YcfhnndWA 2ms7660kbC++201.4kb2024-10-07 11:25:122024-10-07 11:25:12

Judging History

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

  • [2024-10-07 11:25:12]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7660kb
  • [2024-10-07 11:25:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int N = 5e5 + 10;
int n, m;
vector<pair<int, int>>adj[N];

int dfn[N], low[N], col[N], cnt, tot;
vector<int>dcc[N];
stack<int>s;
set<array<int, 2>>bridge;
void dfs(int u, int las){
    dfn[u] = low[u] = ++ cnt;
    s.push(u);
    for (auto [v, w] : adj[u]){
        if (w == (las ^ 1)) continue;
        if (dfn[v] == -1){
            dfs(v, w);
            low[u] = min(low[u], low[v]);
        } else{
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]){
        tot ++;
        int y;
        do{
            y = s.top();
            s.pop();
            col[y] = tot;
            dcc[tot].push_back(y);
        }while (y != u);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1;i <= m;i ++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i << 1 });
        adj[v].push_back({u, i << 1 | 1});
    }

    for (int i = 0;i <= n;i ++){
        dfn[i] = -1;
    }

    for (int i = 0;i <= n - 1;i ++){
        if (dfn[i] == -1){
            dfs(i, 0);
        }
    }

    cout << tot << "\n";
    for (int i = 1;i <= tot;i ++){
        cout << dcc[i].size() << " ";
        for (auto c : dcc[i]){
            cout << c << " ";
        }
        cout << "\n";
    }

    return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 7660kb

input:

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

output:

4
2 3 0 
1 5 
1 2 
2 4 1 

result:

wrong answer 4 is later than 2, but there is an edge (4, 2)