QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639551 | #999. 边双连通分量 | Bovmelo | WA | 0ms | 3600kb | C++23 | 1.3kb | 2024-10-13 20:21:06 | 2024-10-13 20:21:08 |
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);
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'