Graph Cutting

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
struct Bridges {
	vector<int> c, h;
	void dfs(vector<pair<int, int>>* g, int x, int pe, int d, vector<int>& ns) {
		if (h[x]) return;
		h[x] = d; ns.push_back(x);
		for (auto nx:g[x]) {
			if (nx.S!=pe) {
				dfs(g, nx.F, nx.S, d+1, ns);
				h[x]=min(h[x], h[nx.F]);
			}
		}
		if (h[x]==d) {
			while (ns.size()>0) {
				int t=ns.back();c[t]=x;
				ns.pop_back();
				if(t==x) break;
			}
		}
	}
	Bridges(vector<pair<int,int>>* g, int n): c(n+1), h(n+1) {
		vector<int> ns;
		for (int i = 1; i<=n;i++) dfs(g, i, -1, 1, ns);
	}
};
struct Biconnected {
	vector<int> cut, h, d, used;
	vector<map<int, vector<int>>> bg;
	vector<pair<int,int>> es;
	int cc;
	void dfs(vector<int>* g, int x, int p) {
		h[x]=d[x];
		int f=0;
		for(int nx:g[x]) {
			if(nx!=p) {
				if (!used[nx]) es.push_back({x, nx});
				if (d[nx]==0) {
					f++; d[nx]=d[x]+1;
					int ts=es.size();
					dfs(g, nx, x);
					h[x]=min(h[x], h[nx]);
					if (h[nx]>=d[x]) {
						cut[x]=1;
						while((int)es.size()>=ts) {
							auto e=es.back();
							bg[e.F][cc].push_back(e.S);
							bg[e.S][cc].push_back(e.F);
							used[e.S]=1;used[e.F]=1;
							es.pop_back();
						}
						used[x]=0;cc++;
					}
				}
				h[x]=min(h[x], d[nx]);
			}
		}
		if (p==0) {
			if (f>1) cut[x]=1;
			else cut[x]=0;
		}
	}
	Biconnected(vector<int>* g, int n) : cut(n+1), h(n+1), d(n+1), used(n+1), bg(n+1) {
		cc=1;
		for (int i=1;i<=n;i++) {
			if (d[i]==0) {
				d[i]=1;dfs(g, i, 0);
			}
		}
	}
						
};

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int,int>>> g1(n+1);
	vector<vector<int>> g2(n+1);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		g1[a].push_back({b, i});
		g1[b].push_back({a, i});
		g2[a].push_back(b);
		g2[b].push_back(a);
	}

	Bridges b(g1.data(), n);
	Biconnected c(g2.data(), n);

	int r1 = 0;
	int r2 = 0;
	for (int v = 1; v <= n; v++) {
		for (auto e : g1[v]) {
			if (b.c[v] != b.c[e.F])
				r1++;
		}
	}
	r1 /= 2;
	//for (int a : c.cut) cout << a << " "; cout<<endl;
	//for (int a : c.h) cout << a << " "; cout<<endl;
	//for (int a : c.d) cout << a << " "; cout<<endl;
	//for (int a : c.used) cout << a << " "; cout<<endl;
	for (int v = 1; v <= n; v++) {
		r2 += c.cut[v];
	}

	cout << r2 << " " << r1 << endl;
}

Test 1

Verdict: ACCEPTED