QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#637537#906. 强连通分量BovmeloWA 323ms58136kbC++231.2kb2024-10-13 13:15:552024-10-13 13:15:55

Judging History

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

  • [2024-10-13 13:15:55]
  • 评测
  • 测评结果:WA
  • 用时:323ms
  • 内存:58136kb
  • [2024-10-13 13:15:55]
  • 提交

answer

// Nothing is Given, Everything is Earned.
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, m; cin >> n >> m;
    vector<vector<int>> e(n);
    for(int i = 1; i <= m; i++)
    {
        int u, v; cin >> u >> v;
        e[u].push_back(v);
    }

    vector<int> dfn(n), low(n), bel(n, -1);
    int dfx = 0;
    stack<int> st;
    vector<vector<int>> scc;

    function<void(int, int)> dfs = [&](int u, int fa)
    {
        dfn[u] = low[u] = ++dfx;
        st.push(u);
        for(int v : e[u])
        {
            if(!dfn[v]) dfs(v, u), low[u] = min(low[u], low[v]);
            else if(!~bel[v]) low[u] = min(low[u], dfn[v]);
        }
        if(dfn[u] == low[u])
        {
            vector<int> res;
            do
            {
                bel[st.top()] = scc.size();
                res.push_back(st.top());
                st.pop();
            } while(res.back() != u);
            scc.push_back(res);
        }
    };
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) dfs(i, i);

    cout << scc.size() << "\n";
    for(auto v : scc | views::reverse)
    {
        cout << v.size() << " ";
        for(int i : v) cout << i << " ";
        cout << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

input:

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

output:

4
1 5 
2 0 3 
2 4 1 
1 2 

result:

ok OK

Test #2:

score: -100
Wrong Answer
time: 323ms
memory: 58136kb

input:

500000 500000
389812 410922
255712 339244
274009 248522
347288 199231
235313 301629
469588 84917
364188 449407
392348 436920
26220 198288
162188 468965
274222 92196
463222 408478
231663 467768
382681 38083
412497 160479
280851 268689
101149 25450
62271 9177
38892 268598
273853 250782
191939 89247
40...

output:

499591
1 500000 
1 499999 
1 499995 
1 499994 
1 499989 
1 499988 
1 499987 
1 499983 
1 499978 
1 499975 
1 499972 
1 499969 
1 499965 
1 499964 
1 499954 
1 499949 
1 499947 
1 499942 
1 499939 
1 499932 
1 499928 
1 499926 
1 499925 
1 499924 
1 499919 
1 499918 
1 499915 
1 499910 
1 499909 
1 4...

result:

wrong answer Integer 500000 violates the range [0, 499999]