#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;
int timer=0;
void dfs(int x, int p) {
num[x] = ++timer;
lowpt[x] = num[x];
for(auto e : graph[x]) {
if(e != p) {
if(num[e]) lowpt[x] = min(lowpt[x], num[e]);
else {
dfs(e, x);
lowpt[x] = min(lowpt[x], lowpt[e]);
}
}
}
if(p && lowpt[x] >= num[x]) bridg.pb(mp(p, x));
}
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);
}
}
lowpt = num = vi(n+1);
forr(i, 1, n+1) {
if(!num[i]) dfs(i, 0);
}
for(auto p : bridg) printf("%d %d\n", p.f, p.s);
}
Compilation message
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:71:5: note: in expansion of macro 'scd'
71 | 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:72:5: note: in expansion of macro 'scd'
72 | 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:82:9: note: in expansion of macro 'scd'
82 | 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:83:9: note: in expansion of macro 'scd'
83 | scd(b);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
860 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
604 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
668 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
656 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
1620 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
266 ms |
3664 KB |
Output is correct |
| 2 |
Runtime error |
214 ms |
17256 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
363 ms |
9812 KB |
Output is correct |
| 2 |
Runtime error |
285 ms |
24676 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
539 ms |
11284 KB |
Output is correct |
| 2 |
Runtime error |
556 ms |
41736 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
652 ms |
14068 KB |
Output is correct |
| 2 |
Runtime error |
616 ms |
50392 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
908 ms |
17820 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
975 ms |
30036 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
