QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#639551#999. 边双连通分量BovmeloWA 0ms3600kbC++231.3kb2024-10-13 20:21:062024-10-13 20:21:08

Judging History

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

  • [2024-10-13 20:21:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3600kb
  • [2024-10-13 20:21:06]
  • 提交

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);
        e[v].push_back(u);
    }

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

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

    cout << bcc.size() << "\n";
    for(auto v : bcc)
    {
        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: 3600kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

1
4 3 2 1 0 

result:

ok OK

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3572kb

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

2
6 11 4 5 1 9 0 
7 6 7 8 10 3 12 2 

result:

wrong answer # of tecc is differ - expected: '3', found: '2'