# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
388503 | 2021-04-11T18:28:43 Z | armanmohammadi | Pipes (CEOI15_pipes) | C++14 | 0 ms | 0 KB |
/* _________ .---""" """---. :______.-': : .--------------. : | ______ | | : : | |:______B:| | | Little Error: | | |:______B:| | | | | |:______B:| | | Power not | | | | | | found. | | |:_____: | | | | | | == | | : : | | O | : '--------------' : | o | :'---...______...---' | o |-._.-i___/' \._ |'-.____o_| '-. '-...______...-' `-._ :_________: `.____________________ `-.___.-. .'.eeeeeeeeeeeeeeeeee.'. :___: fsc .'.eeeeeeeeeeeeeeeeeeeeee.'. :____________________________: */ //in the name of god //if you read this code please search about imam hussain #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define endl "\n" #define X first #define Y second #define pii pair<int,int> #define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout) const int maxn=6 000 000+5; const int mod=1e9+7; const int inf=1e9; const int del=728729; ll poww(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));} ll par[maxn][2] ; ll par2[maxn][2] ; ll mark[maxn] ; ll an; vector<int>adj[maxn]; int n ; int m ; int getPar(int v){ if(par[v][an] == v){ return v ; }else return par[v][an] = getPar(par[v][an]); } bool merge(int u, int v){ u = getPar(u); v = getPar(v); if (u == v){ return false; } par[u][an] = v; return true; } void dfs(int v, int p = 0){ mark[v] = 1; par2[v][1] = maxn; int cnt ; for (int u : adj[v]){ if (u == p){ cnt ++; continue; } if (mark[u]){ par2[v][1] = min(par2[v][1], par2[u][0]); } else{ par2[u][0] = par2[v][0] + 1; dfs(u, v); par2[v][1] = min(par2[v][1], par2[u][1]); } } if (p and cnt == 1 and par2[p][0] < par2[v][1]){ cout << p << " " << v << endl; } } int main(){ migmig ; cin >> n >> m; for (int i = 0; i < maxn; i ++){ par[i][0] = par[i][1] = i; } for (int i = 0; i < m; i ++){ int u ; int v ; bool flag = true; cin >> u >> v; an = 0; if (merge(u, v)){ adj[u].pb(v); adj[v].pb(u); flag = 0; } an = 1; if (flag and merge(u, v)){ adj[u].pb(v); adj[v].pb(u); } } for (int v = 1; v <= n; v ++){ if (!mark[v]){ dfs(v); } } return 0; }