Submission #1265416

#TimeUsernameProblemLanguageResultExecution timeMemory
1265416escobrandPipes (CEOI15_pipes)C++20
80 / 100
560 ms19936 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(),v.end() #define pb push_back #define ll long long #define ld long double #define fi first #define se second #define mk make_pair typedef pair<int,int> pii; const int maxn = 1e5 + 10; int i,n,t,m,low[maxn],tim[maxn],u,v; vector<int> adj[maxn]; struct DSU { int p[maxn]; DSU(int n) { for(int i = 1;i<=n;i++)p[i] = i; } int fi(int i) { while(i != p[i])i = p[i] = p[p[i]]; return i; } bool unite(int u,int v) { u = fi(u); v = fi(v); if(u == v)return 0; p[v] = u; return 1; } }; void dfs(int i,int pa) { tim[i] = low[i] = ++t; bool ch = 0; for(const int &k : adj[i]) { if(k == pa && !ch) { ch = 1; continue; } if(tim[k])low[i] = min(low[i],tim[k]); else { dfs(k,i); low[i] = min(low[i],low[k]); if(low[k] == tim[k])cout<<i<<' '<<k<<'\n'; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; DSU a(n),b(n); while(m--) { cin>>u>>v; if(a.unite(u,v) || b.unite(u,v)) { adj[u].pb(v); adj[v].pb(u); } } for(i = 1;i<=n;i++) { if(!tim[i]) { dfs(i,0); } } 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...