QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#618891 | #906. 强连通分量 | Ycfhnnd | WA | 2ms | 7660kb | C++20 | 1.4kb | 2024-10-07 11:25:12 | 2024-10-07 11:25:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 5e5 + 10;
int n, m;
vector<pair<int, int>>adj[N];
int dfn[N], low[N], col[N], cnt, tot;
vector<int>dcc[N];
stack<int>s;
set<array<int, 2>>bridge;
void dfs(int u, int las){
dfn[u] = low[u] = ++ cnt;
s.push(u);
for (auto [v, w] : adj[u]){
if (w == (las ^ 1)) continue;
if (dfn[v] == -1){
dfs(v, w);
low[u] = min(low[u], low[v]);
} else{
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]){
tot ++;
int y;
do{
y = s.top();
s.pop();
col[y] = tot;
dcc[tot].push_back(y);
}while (y != u);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= m;i ++){
int u, v;
cin >> u >> v;
adj[u].push_back({v, i << 1 });
adj[v].push_back({u, i << 1 | 1});
}
for (int i = 0;i <= n;i ++){
dfn[i] = -1;
}
for (int i = 0;i <= n - 1;i ++){
if (dfn[i] == -1){
dfs(i, 0);
}
}
cout << tot << "\n";
for (int i = 1;i <= tot;i ++){
cout << dcc[i].size() << " ";
for (auto c : dcc[i]){
cout << c << " ";
}
cout << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7660kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 3 0 1 5 1 2 2 4 1
result:
wrong answer 4 is later than 2, but there is an edge (4, 2)