QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#637534#906. 强连通分量BovmeloWA 0ms3604kbC++231.2kb2024-10-13 13:14:372024-10-13 13:14:37

Judging History

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

  • [2024-10-13 13:14:37]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3604kb
  • [2024-10-13 13:14:37]
  • 提交

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)
    {
        cout << v.size() << " ";
        for(int i : v) cout << i << " ";
        cout << "\n";
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3604kb

input:

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

output:

4
1 2 
2 4 1 
2 0 3 
1 5 

result:

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