Graph Cutting

input/code.cpp: In function 'bool dfs1(int, int)':
input/code.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < conns[i].size(); ++j) {
                                    ^
input/code.cpp: In function 'int dfs2(int, int, int&)':
input/code.cpp:28:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < conns[i].size(); ++j) {
                                    ^

#include <iostream>
#include <vector>

const int N = 1e5;
int tim[N];
std::vector<int> conns [N];
int bridges = 0;
int articul = 0;

bool dfs1(int i, int b) {
	if (tim[i] == -1) return false;
	if (i == b) return false;
	tim[i] = -1;
	for (int j = 0; j < conns[i].size(); ++j) {
		int t = conns[i][j];
		dfs1(t, b);
	}
	return true;
}

// returns smallest tim found from sub"tree"
// counts number of bridges and articulation points (hopefully)
int dfs2(int i, int p, int& tick) {
	tim[i] = tick;
	int min = tick;
	++tick;
	bool blocks = false;
	for (int j = 0; j < conns[i].size(); ++j) {
		int t = conns[i][j];
		if (t == p) continue;
		if (tim[t] != -1) {
			min = std::min(tim[t], min);
			continue;
		}
		int sub = dfs2(t, i, tick);
		if (sub > tim[i]) { 
			++bridges;
			// std::cout << "bridge " << sub << ' ' << (i+1) << ' ' << (t+1) << '\n';
		}
		if (sub >= tim[i]) { blocks = true; }
		else { min = std::min(sub, min); }
	}
	if (blocks) {
		// std::cout << "articul i p min " << (i+1) << ' ' << (p+1) << ' ' << min << '\n';
		++articul;
	}
	return min;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	int n, m;
	std::cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		std::cin >> a >> b;
		--a; --b;
		conns[a].push_back(b);
		conns[b].push_back(a);
	}
	if (n == 1) {
		std::cout << "0 0\n";
	} else {
		// check that the graph is connected
		int comp = 0;
		for (int i = 0; i < n; ++i) {
			if (dfs1(i, -1)) ++comp;
		}
		if (comp > 1) {
			std::cout << "0 0\n";
		} else {
			int tick = 0;
			dfs2(0, 0, tick);
			dfs1(conns[0][0], 0);
			tick = 0;
			for (int i = 1; i < n; ++i) {
				if (tim[i] != -1) ++tick;
			}
			if (tick == 0) --articul;
			std::cout << articul << ' ' << bridges << '\n';
		}
	}
}

Test 1

Verdict: ACCEPTED