#include "bits/stdc++.h"
using namespace std;
int *par;
int *bic;
vector <int> *g;
int *low, *disc;
bitset <100005> vis;
vector <int> l, r;
int root(int x, int *a) {
if(a[x] == x) return x;
return a[x] = root(a[x], a);
}
void join(int x, int y, int *a) {
x = root(x, a);
y = root(y, a);
if(x != y) {
a[x] = y;
}
}
int tym;
void dfs(int x, int parent) {
vis[x] = 1;
low[x] = disc[x] = ++tym;
bool see = false;
for(auto i : g[x]) {
if (!see && i == parent) {
see = true;
continue;
}
if(vis[i] == 0) {
dfs(i, x);
low[x] = min(low[x], low[i]);
if(disc[x] < low[i]) {
l.push_back(x);
r.push_back(i);
}
} else if (vis[i] == 1) {
low[x] = min(low[x], disc[i]);
}
}
}
int main(int argc, char const *argv[])
{
int n, m;
scanf("%d %d", &n, &m);
par = new int [n + 5];
bic = new int [n + 5];
for(int i = 1; i <= n; i++) {
par[i] = i;
bic[i] = i;
}
for(int i = 1; i <= m; i++) {
int p, q;
scanf("%d %d", &p, &q);
if(root(p, par) != root(q, par)) {
join(p, q, par);
l.push_back(p);
r.push_back(q);
} else if (root(q, bic) != root(p, bic)) {
join(p, q, bic);
l.push_back(p);
r.push_back(q);
}
}
exit(0);
delete par;
delete bic;
g = new vector <int> [n + 5];
for(size_t i = 0; i < l.size(); i++) {
g[l[i]].push_back(r[i]);
g[r[i]].push_back(l[i]);
}
l.clear();
r.clear();
low = new int [n + 5];
disc = new int [n + 5];
for(int i = 1; i <= n; i++) {
if(vis[i] == 0) {
dfs(i, 0);
}
}
for(size_t i = 0; i < l.size(); i++) {
printf("%d %d\n", l[i], r[i]);
}
delete low;
delete disc;
return 0;
}
Compilation message
pipes.cpp: In function 'int main(int, const char**)':
pipes.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &p, &q);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
668 KB |
Output is correct |
| 2 |
Incorrect |
112 ms |
616 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
198 ms |
924 KB |
Output is correct |
| 2 |
Incorrect |
232 ms |
820 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
1136 KB |
Output is correct |
| 2 |
Incorrect |
275 ms |
1288 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
549 ms |
2760 KB |
Output is correct |
| 2 |
Incorrect |
387 ms |
2800 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
838 ms |
2836 KB |
Output is correct |
| 2 |
Incorrect |
703 ms |
2104 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
933 ms |
2908 KB |
Output is correct |
| 2 |
Incorrect |
874 ms |
2932 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1461 ms |
2992 KB |
Output is correct |
| 2 |
Incorrect |
1142 ms |
2916 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1462 ms |
2804 KB |
Output is correct |
| 2 |
Incorrect |
1355 ms |
2932 KB |
Wrong number of edges |
