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;
const int N = 1e5 + 1;
int h[N], mnh[N], edges;
bool vis[N];
vector<pair<int, int>> g[N];
int root1(int& v){
return (h[v] == -1 ? v : h[v] = root1(h[v]));
}
int root2(int& v){
return (mnh[v] == -1 ? v : mnh[v] = root2(mnh[v]));
}
void merge1(int& u, int& v){
int r1 = root1(v);
int r2 = root1(u);
h[r1] = r2;
edges++;
g[v].push_back({u, edges});
g[u].push_back({v, edges});
}
void merge2(int& u, int& v){
int r1 = root2(u);
int r2 = root2(v);
if (r1 == r2)
return;
mnh[r1] = r2;
edges++;
g[v].push_back({u, edges});
g[u].push_back({v, edges});
}
void dfs(int v, pair<int, int> prev = {-1, -1}){
vis[v] = 1;
if (prev.first == -1)
h[v] = 0;
mnh[v] = h[v];
for (pair<int, int> p : g[v]){
int u = p.first;
int id = p.second;
if (prev.first == u and prev.second == id)
continue;
mnh[v] = min(mnh[v], h[u]);
if (vis[u])
continue;
h[u] = h[v] + 1;
dfs(u, {v, id});
mnh[v] = min(mnh[v], mnh[u]);
if (mnh[u] >= h[u])
printf("%d %d\n", u, v);
}
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++)
h[i] = mnh[i] = -1;
for (int i=0; i<m; i++){
int u, v;
scanf("%d%d", &u, &v);
if (root1(u) != root1(v))
merge1(u, v);
else if (root2(u) != root2(v))
merge2(u, v);
}
for (int i=1; i<=n; i++)
h[i] = mnh[i] = n + 100;
for (int v = 1; v <= n; v++)
if (!vis[v])
dfs(v);
}
Compilation message (stderr)
pipes.cpp: In function 'int main()':
pipes.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
# | 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... |