2015 ACM Amman Collegiate Programming Contest ( H.Bridge)

Problem link: H. Bridges

Idea: 

 First, find all bridges in the given graph, then remove them from the graph and find all components of the resulting graph.

Consider each component as a single vertex and add the bridges again, now you have a tree where all edges are bridges (in the original graph).
In the resulting tree, to make an edge not a bridge, it has to be in a cycle, and since all edges in this cycle won't become bridges anymore, you have to create the largest possible cycle, so find the longest path in the tree, and connect it's endpoints. Final answer is : Total number of bridges — length of resulting cycle + 1
Which is equal to : Total number of bridges — longest path in tree.

	/// Topic: DSU + bridge + dfs
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg1(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	template < typename F, typename S >
	ostream& operator << ( ostream& os, const pair< F, S > & p ) {
	return os << "(" << p.first << ", " << p.second << ")";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << *it;
	}
	return os << "}";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin()) os << ", ";
	os << *it;
	}
	return os << "]";
	}
	template < typename F, typename S >
	ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << it -> first << " = " << it -> second ;
	}
	return os << "]";
	}
	#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
	clock_t tStart = clock();
	#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
	void faltu () { cerr << endl; }
	template <typename T>
	void faltu( T a[], int n ) {
	for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
	cerr << endl;
	}
	template <typename T, typename ... hello>
	void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
	// Program showing a policy-based data structure.
	#include <ext/pb_ds/assoc_container.hpp> // Common file
	#include <ext/pb_ds/tree_policy.hpp>
	#include <functional> // for less
	#include <iostream>
	using namespace __gnu_pbds;
	using namespace std;
	// GNU link : https://goo.gl/WVDL6g
	typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update>
	new_data_set;
	/**___________________________________________________**/
	ll visited[maxn];
	int parent[maxn];
	ll longest, mx;
	vector<int> graph[maxn], Tree[maxn];
	ll dist[maxn];
	ll low[maxn];
	ll best[maxn][2];
	set<pair<int, int> > ans;
	ll cnt;
	int n, m;
	struct subset
	{
	int parent;
	int rank;
	} subsets[maxn];
	inline void Clear()
	{
	for (int i = 0; i < maxn; i++) {
	visited[i] = 0;
	parent[i] = -1;
	graph[i].clear();
	Tree[i].clear();
	best[i][0] = best[i][1] = 0;
	}
	ans.clear();
	mx = -1;
	cnt = 0;
	longest = 0;
	}
	inline void Input()
	{
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
	int u, v;
	cin >> u >> v;
	graph[u].push_back(v);
	graph[v].push_back(u);
	}
	}
	inline void initializer()
	{
	for (int i = 1; i <= n; i++) {
	subsets[i].parent = i;
	subsets[i].rank = 0;
	}
	}
	inline int find(int x)
	{
	if (subsets[x].parent != x)
	subsets[x].parent = find(subsets[x].parent);
	return subsets[x].parent;
	}
	inline void Union(int x, int y)
	{
	x = find(x);
	y = find(y);
	if (subsets[x].rank > subsets[y].rank)
	subsets[y].parent = x;
	else if (subsets[x].rank < subsets[y].rank)
	subsets[x].parent = y;
	else {
	subsets[x].parent = y;
	subsets[y].rank++;
	}
	}
	inline void bridge(int u)
	{
	static ll Time = 0;
	visited[u] = 1;
	dist[u] = low[u] = ++Time;
	for (auto v : graph[u]) {
	if (!visited[v]) {
	parent[v] = u;
	bridge(v);
	low[u] = min(low[u], low[v]);
	if (low[v] > dist[u]) {
	cnt++;
	ans.insert({u, v});
	ans.insert({v, u});
	}
	}
	else {
	if (v != parent[u])
	low[u] = min(low[u], dist[v]);
	}
	}
	}
	inline void DSU()
	{
	for (int i = 1; i <= n; i++) {
	for (auto v : graph[i]) {
	if (ans.find({i, v}) == ans.end()) {
	int x = find(i);
	int y = find(v);
	if (x != y)
	Union(x, y);
	}
	}
	}
	}
	inline void dfs(int u)
	{
	visited[u] = 1;
	for (auto v : Tree[u]) {
	if (visited[v]) continue;
	dfs(v);
	if (best[v][0] + 1 > best[u][0]) {
	best[u][1] = best[u][0];
	best[u][0] = best[v][0] + 1;
	}
	else if (best[v][0] + 1 > best[u][1])
	best[u][1] = best[v][0] + 1;
	}
	longest = max(longest, best[u][0] + best[u][1]);
	}
	int main()
	{
	FASTIO
	///*
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//scanf("%d", &T);
	T = 1;
	cin >> T;
	for (int cs = 1; cs <= T; cs++) {
	Clear();
	Input();
	for (int i = 1; i <= n; i++) {
	if (!visited[i]) bridge(i);
	}
	initializer();
	DSU();
	for (auto x : ans) {
	int u = find(x.first);
	int v = find(x.second);
	if (u != v)
	Tree[u].push_back(v);
	}
	memset(visited, 0, sizeof visited);
	for (int i = 1; i <= n; i++) {
	if (!visited[i])
	dfs(i);
	}
	cout << cnt - longest << endl;
	}
	return 0;
	}

view raw H.bridge hosted with ❤ by GitHub

 

Share: