제출 #169421

#제출 시각아이디문제언어결과실행 시간메모리
169421gs18103Pipes (CEOI15_pipes)C++14
100 / 100
1636 ms14040 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MX=100010, inf=2e9; int n, m; int U[2][MX]; vector<int> G[MX]; int find(int t, int x){ return x==U[t][x] ? x : U[t][x]=find(t,U[t][x]); } void unite(int t, int x, int y){ if(find(t,x)==find(t,y)) return; U[t][U[t][y]]=U[t][x]; } int up[MX], dep[MX], now; void dfs(int v, int p){ dep[v]=++now; up[v]=dep[v]; bool multi=false; for(int x:G[v]){ if(x==p){ if(multi) up[v]=min(up[v], dep[p]); multi=true; continue; } if(dep[x]>0) up[v]=min(up[v], dep[x]); else{ dfs(x,v); up[v]=min(up[v], up[x]); if(up[x]>dep[v]) cout<<v<<' '<<x<<'\n'; } } now--; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1; i<=n; i++) U[0][i]=U[1][i]=i; for(int i=1; i<=m; i++){ int u, v; cin>>u>>v; if(find(0,u)==find(0,v)){ if(find(1,u)==find(1,v)) continue; unite(1,u,v); } else unite(0,u,v); G[u].push_back(v); G[v].push_back(u); } for(int i=1; i<=n; i++) if(dep[i]==0) dfs(i,-1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...