제출 #86630

#제출 시각아이디문제언어결과실행 시간메모리
86630arafat_01Pipes (CEOI15_pipes)C++17
20 / 100
1552 ms65536 KiB
#include <bits/stdc++.h>

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const ll inf = 1e18 + 9;

inline void boost () {
	ios_base::sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
}
int n, m;
vector < vector < int > > g;
vector < bool > used;
vector < int > tin, fup;
int timer;
map < pair < int , int >, int > cnt;
vector < pair < int, int > > ans;

void dfs (int v, int pr = 0) {
	used[v] = 1;
	tin[v] = fup[v] = ++ timer;
	for (auto to : g[v]) {
		if (to == pr) continue;
		if (used[to]) {
			fup[v] = min (fup[v], tin[to]);		
		} else {
			dfs (to, v);
			fup[v] = min (fup[v], fup[to]);
			if (fup[to] > tin[v] && cnt[mp (v, to)] <= 1) {
				ans.pb (mp (v, to));
			}
		}
	}

}

int main () {
 	boost ();
 	cin >> n >> m;
  int u, v;
  g.resize (n + 1);
  used.resize (n + 1);
  tin.resize (n + 1);
  fup.resize (n + 1);
	for (int i = 1;i <= m;i ++) {
		cin >> u >> v;
 		g[u].pb (v);
 		g[v].pb (u);
 		cnt[mp (u, v)] ++;
 		cnt[mp (v, u)] ++;
 	}
 	for (int i = 1;i <= n;i ++) {
 		if (!used[i]) dfs (i);
 	}
	for (auto it : ans) cout << it.F << ' ' << it.S << endl; 	 	

	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...