#include <bits/stdc++.h>
using namespace std;
#define mod 1000007
#define oo 2000000000
const int N = 100010 , LOGN = 18;
bitset< N > bridge;
int dp[LOGN][N] , prnt[N] , num[N] , cur[N] , depth[N];
vector< pair<int,int> > t[N];
int find(int a){
return (a == prnt[a] ? a : prnt[a] = find(prnt[a]));
}
int DFS(int node,int prnt){
int sum = 0 , s = 0;
for(int i=0;i<t[node].size();i++){
if(t[node][i].first == prnt) continue;
s = DFS(t[node][i].first,node);
if(s > 0) bridge[t[node][i].second] = false;
sum += s;
}
sum+= cur[node];
cur[node] = 0 ;
return sum;
}
void DFS2(int node,int pr,int pr2,int d){
dp[0][node] = pr;
depth[node] = d;
for(int j=1;(1 << j) <= num[pr2];j++){
if(dp[j-1][node] == -1)
dp[j][node] = -1;
else
dp[j][node] = dp[j-1][dp[j-1][node]];
}
prnt[node] = pr2;
for(int i=0;i<t[node].size();i++){
if(t[node][i].first == pr) continue;
DFS2(t[node][i].first,node,pr2,d+1);
}
}
int lca(int u,int v){
if(depth[u] > depth[v]) swap(u,v);
for(int i=LOGN-1;i>=0;i--){
if(depth[u] + (1 << i) <= depth[v]) v = dp[i][v] ;
}
if(u == v) return u;
for(int i=LOGN-1;i>=0;i--){
if(dp[i][u] != dp[i][v]){
u = dp[i][u];
v = dp[i][v];
}
}
return dp[0][u];
}
int main() {
//freopen("in.txt","r",stdin);
int n , m , cnt = 0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
prnt[i] = i;
dp[0][i] = -1;
num[i] = 1;
}
int u , v;
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
int a= find(u);
int b= find(v);
if(a == b){
cur[v]++;
cur[u]++;
cur[lca(u,v)]-=2;
}
else{
bridge[cnt] = true;
t[u].push_back(make_pair(v,cnt));
t[v].push_back(make_pair(u,cnt++));
if(num[a] > num[b]){
DFS(v,u);
DFS2(v,u,a,depth[u] + 1);
num[a] += num[b];
num[b] = 0 ;
}
else{
DFS(u,v);
DFS2(u,v,b,depth[v] + 1);
num[b] += num[a];
num[a] = 0 ;
}
}
}
for(int i=1;i<=n;i++){
if(prnt[i] == i){
DFS(i,-1);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<t[i].size();j++){
if(i > t[i][j].first) continue;
if(bridge[t[i][j].second]){
printf("%d %d\n",i,t[i][j].first);
}
}
}
return 0;
}
Compilation message
pipes.cpp: In function 'int DFS(int, int)':
pipes.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<t[node].size();i++){
~^~~~~~~~~~~~~~~
pipes.cpp: In function 'void DFS2(int, int, int, int)':
pipes.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<t[node].size();i++){
~^~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t[i].size();j++){
~^~~~~~~~~~~~
pipes.cpp:61: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2688 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
3200 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
3200 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
3072 KB |
Output is correct |
| 2 |
Incorrect |
188 ms |
3112 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
416 ms |
3712 KB |
Output is correct |
| 2 |
Incorrect |
476 ms |
3712 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
771 ms |
5404 KB |
Output is correct |
| 2 |
Correct |
624 ms |
6180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1255 ms |
11072 KB |
Output is correct |
| 2 |
Incorrect |
1106 ms |
10744 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1975 ms |
12324 KB |
Output is correct |
| 2 |
Correct |
1649 ms |
12112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2834 ms |
14508 KB |
Output is correct |
| 2 |
Incorrect |
2916 ms |
14556 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3823 ms |
14596 KB |
Output is correct |
| 2 |
Incorrect |
3827 ms |
14712 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4673 ms |
13900 KB |
Output is correct |
| 2 |
Correct |
3993 ms |
14520 KB |
Output is correct |
