QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424680#906. 强连通分量AdorableWA 2ms7704kbC++231.6kb2024-05-29 15:22:492024-05-29 15:22:54

Judging History

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

  • [2024-05-29 15:22:54]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7704kb
  • [2024-05-29 15:22:49]
  • 提交

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)