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 n, m, h[N], mnh[N], edges, u, v, i, r1, r2, rut, cur, nxt;
bool vis[N];
vector<pair<int, int>> g[N];
int root1(int& v){
rut = v;
cur = v;
while (h[rut]!=-1)
rut = h[rut];
while (h[cur]!=-1){
nxt = h[cur];
h[cur] = rut;
cur = nxt;
}
return rut;
}
int root2(int& v){
rut = v;
cur = v;
while (mnh[rut]!=-1)
rut = mnh[rut];
while (mnh[cur]!=-1){
nxt = mnh[cur];
mnh[cur] = rut;
cur = nxt;
}
return rut;
}
void merge1(int& u, int& v){
r1 = root1(v);
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){
r1 = root2(u);
r2 = root2(v);
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 (auto& [u, id] : g[v]){
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(){
scanf("%d%d", &n, &m);
for (i=1; i<=n; i++)
h[i] = mnh[i] = -1;
for (i=0; i<m; i++){
scanf("%d%d", &u, &v);
if (root1(u) != root1(v))
merge1(u, v);
else if (root2(u) != root2(v))
merge2(u, v);
}
for (i=1; i<=n; i++)
h[i] = mnh[i] = n + 100;
for (v = 1; v <= n; v++)
if (!vis[v])
dfs(v);
}
Compilation message (stderr)
pipes.cpp: In function 'int main()':
pipes.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | 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... |