Submission #3016274

---

Source Code Expand

#include <cassert>
#include <utility>

template <template <class> class Container> class union_find {
protected:
	class node_type;

public:
	using container_type = Container<node_type>;
	using size_type = typename container_type::size_type;

protected:
	class node_type {
	public:
		size_type parent;
		size_type size;
	};

	container_type tree;

public:
	union_find() : tree() {}
	explicit union_find(const size_type size) : tree(size, { 0, 1 }) {
		for (size_type i = 0; i < size; ++i)
			tree[i].parent = i;
	}

	bool empty() const { return tree.empty(); }
	size_type size() const { return tree.size(); }

	size_type find(size_type x) {
		assert(x < size());
		while (tree[x].parent != x)
			x = tree[x].parent = tree[tree[x].parent].parent;
		return x;
	}
	bool same(const size_type x, const size_type y) {
		assert(x < size());
		assert(y < size());
		return find(x) == find(y);
	}
	size_type size(const size_type x) {
		assert(x < size());
		return tree[find(x)].size;
	}

	::std::pair<size_type, size_type> unite(size_type x, size_type y) {
		assert(x < size());
		assert(y < size());
		x = find(x);
		y = find(y);
		if (x != y) {
			if (tree[x].size < tree[y].size)
				::std::swap(x, y);
			tree[x].size += tree[y].size;
			tree[y].parent = x;
		}
		return { x, y };
	}
};

#include<iostream>
#include<cstdint>
#include<vector>
template<class T>
using vec_alias = ::std::vector<T>;

int main() {
	using u32 = ::std::uint_fast32_t;
	using u64 = ::std::uint_fast64_t;
	u32 n, m;
	::std::cin >> n >> m;
	union_find<vec_alias> uf(n * 2);

	for (u32 i = 0;i < m;++i) {
		u32 a, b;
		::std::cin >> a >> b;
		--a;
		--b;
		uf.unite(a, b + n);
		uf.unite(a + n, b);
	}

	if (uf.same(0, n)) {
		::std::cout << static_cast<u64>(n)*(n - 1) / 2 - m << ::std::endl;
		return 0;
	}

	u64 cnt = 0;
	for (u32 i = 0;i < n;++i)
		if (uf.same(0, i))
			++cnt;

	::std::cout << (static_cast<u64>(n) - cnt) * cnt - m << ::std::endl;

	return 0;
}

Submission Info

Judge Result