This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> AdjList;
vector<int> lowlink, order;
vector<pair<int, int>> bridges;
int N, M, cnt;
void dfs (int node, int padre = -1){
if(padre == -1){
order[node] = 0;
lowlink[node] = 0;
for (int son: AdjList[node]){
if(order[son] != -1) continue;
cnt++;
order[son] = cnt;
dfs(son, node);
if(lowlink[son] > order[node]) bridges.push_back({node, son});
}
}
else{
lowlink[node] = order[node];
for (int son: AdjList[node]){
if(son == padre) continue;
if(order[son] != -1){
lowlink[node] = min(lowlink[node], lowlink[son]);
continue;
}
cnt++;
order[son] = cnt;
dfs(son, node);
if(lowlink[son] > order[node]) bridges.push_back({node, son});
if(lowlink[son] < order[node]){
lowlink[node] = min(lowlink[node], lowlink[son]);
}
}
}
}
int occurrences(int u, int v){
int cnt = 0;
for(int next: AdjList[u]){
if(next == v) cnt++;
}
return cnt;
}
int main(){
cin >> N >> M;
AdjList = vector<vector<int>>(N);
lowlink = vector<int>(N);
order = vector<int>(N, -1);
int u, v;
for(int i = 0; i < M; ++i){
cin >> u >> v; u--; v--;
AdjList[u].push_back(v);
AdjList[v].push_back(u);
}
for(int i = 0; i < N; ++i){
if(order[i] == -1) {
cnt = 0;
dfs(i);
}
}
for(pair<int, int> path: bridges) {
u = path.first; v = path.second;
if(occurrences(u, v) > 1) continue;
cout << path.first + 1 << " " << path.second + 1 << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |