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;
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;
void usaco()
{
freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
// freopen("problem.out", "w", stdout);
}
vvi graph;
vi dis1, dis2;
int findf(int x, vi &dis) {
if(x == dis[x]) return x;
dis[x] = findf(dis[x], dis);
return dis[x];
}
void unionf(int x, int y, vi &dis) {
x = findf(x, dis);
y = findf(y, dis);
dis[y] = x;
}
vii bridg;
vi num, lowpt;
stack<pii> stk;
int timer=0;
void dfs(int x, int y) {
num[y] = ++timer;
lowpt[y] = num[y];
for(auto e : graph[y]) {
if(e == x) continue;
if(num[e] && num[e] < num[y]) {
lowpt[y] = min(lowpt[y], num[e]);
stk.push(mp(y, e));
}
else if(!num[e]) {
stk.push(mp(y, e));
dfs(y, e);
lowpt[y] = min(lowpt[y], lowpt[e]);
}
}
if(x != 0 && lowpt[y] >= num[x]) {
vii edg;
while(stk.top() != mp(x, y)) {
// printf("%d %d\n", stk.top().f, stk.top().s);
edg.pb(stk.top());
stk.pop();
}
// printf("%d %d\n", stk.top().f, stk.top().s);
edg.pb(stk.top());
stk.pop();
// printf("*******************\n");
if(edg.size() == 1) bridg.pb(edg[0]);
}
}
int main() {
// usaco();
int n, m;
scd(n);
scd(m);
graph = vvi(n+1);
dis1 = dis2 = vi(n+1);
forr(i, 1, n+1) {
dis1[i] = dis2[i] = i;
}
frange(i, m) {
int a, b;
scd(a);
scd(b);
// if(findf(a, dis1) != findf(b, dis1)) {
// unionf(a, b, dis1);
// graph[a].pb(b);
// graph[b].pb(a);
// }
// else if(findf(a, dis2) != findf(b, dis2)) {
// unionf(a, b, dis2);
// graph[a].pb(b);
// graph[b].pb(a);
// }
graph[a].pb(b);
graph[b].pb(a);
}
lowpt = num = vi(n+1);
forr(i, 1, n+1) {
if(!num[i]) dfs(0, i);
}
for(auto p : bridg) printf("%d %d\n", p.f, p.s);
}
Compilation message (stderr)
pipes.cpp: In function 'void usaco()':
pipes.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
pipes.cpp:89:5: note: in expansion of macro 'scd'
89 | scd(n);
| ^~~
pipes.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
pipes.cpp:90:5: note: in expansion of macro 'scd'
90 | scd(m);
| ^~~
pipes.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
pipes.cpp:100:9: note: in expansion of macro 'scd'
100 | scd(a);
| ^~~
pipes.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
pipes.cpp:101:9: note: in expansion of macro 'scd'
101 | scd(b);
| ^~~
# | 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... |