QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#637534 | #906. 强连通分量 | Bovmelo | WA | 0ms | 3604kb | C++23 | 1.2kb | 2024-10-13 13:14:37 | 2024-10-13 13:14:37 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)