#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define str string
#define append push_back
#define vi vector<int>
#define int long long
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define endl '\n'
#define all(ls) ls.begin(),ls.end()
#define sorted(ls) sort(ls.begin(),ls.end());
#define reversed(ls) reverse(ls.begin(),ls.end());
#define print(n) for(auto i:n)cout<<i<<' ';cout<<endl;
#define input(n,ls,m) vector<n>ls(m);for(int i=0;i<m;i++)cin>>ls[i];
#define len(s) s.size()
#define ff first
#define ss second
int const N=1e5+10;
int mod=1e9+7;
int mod1=998244353;
int sum_(vector<int>ls){int s=1;for(auto i:ls){s+=i;}return s;}
int min(int a,int b){if (a>b){return b;}return a;}
int max(int a,int b){if (a<b){return b;}return a;}
//......................................tHe ReaL cOdE beGinS HerE....................................../
map<int,bool>visited;
vector<int> graph[N],g[N];
int stree[N],cnt[N],par[N];
int ans=0;
int n;
set<pair<int,int>>s;
void dfs_(int node,int pa){
if(visited[node]) return;visited[node]=1;
for(auto i:g[node]){
int m=visited[i];
dfs_(i,node);
cnt[node]+=cnt[i];
if(!m and !cnt[i]){
s.insert({node,i});
}
}
}
void dfs(int node,int pa){
if(visited[node]) return;
visited[node]=1;
auto it=s.find({pa,node});
par[node]=pa;
if(pa!=-1){
g[pa].append(node);
}
if(it!=s.end()) {
s.erase(it);
s.erase(s.find({node,pa}));
}
stree[node]=1;
for(auto i:graph[node]){
auto m=visited[i];
dfs(i,node);
if(!m) stree[node]+=stree[i];
}
}
void solve(){
int m;
cin>>n>>m;
ans=(n*(n-1))/2;
for(int i=1;i<=n;i++) g[i].clear(),graph[i].clear(),stree[i]=cnt[i]=par[i]=0;
visited.clear();
s.clear();
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
s.insert({u,v});
s.insert({v,u});
graph[u].append(v);
graph[v].append(u);
}
for(int i=1;i<=n;i++){
if(visited[i]) continue;
dfs(i,-1);
}
for(auto [node,pa]:s){
if(stree[pa]<stree[node]) swap(node,pa);
cnt[pa]--;
cnt[node]++;
}
s.clear();
visited.clear();
for(int i=1;i<=n;i++){
if(visited[i])continue;
dfs_(i,-1);
}
for(auto [i,j]:s){
cout<<i<<' '<<j<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)
solve();
}
Compilation message
pipes.cpp: In function 'void dfs_(long long int, long long int)':
pipes.cpp:59:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
59 | if(visited[node]) return;visited[node]=1;
| ^~
pipes.cpp:59:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
59 | if(visited[node]) return;visited[node]=1;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
7260 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
9564 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
9112 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
483 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
490 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
489 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
488 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
522 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
479 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
510 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
531 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
