test/ABC199-D.test.cpp

• View this file on GitHub
• Last update: 2023-03-04 20:28:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc199/submissions/39401194

Depends on

• bipartiteJudge (二部グラフ判定) (src/graph/simple/bipartiteJudge.hpp)
• connectedComponents (連結成分分解 simple ver) (src/graph/simple/connectedComponents.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/graph/simple/bipartiteJudge.hpp"
#include "../src/graph/simple/connectedComponents.hpp"

#include <iostream>

int main() {
	// int N, M; std::cin >> N >> M;
	// std::vector A(M, 0), B(M, 0);
	// for (int i = 0 ; i < M ; i++) {
	// 	std::cin >> A[i] >> B[i];
	// 	A[i]--; B[i]--;
	// }
	// std::vector P(N + 1, 1LL);
	// for (int i = 0 ; i < N ; i++) {
	// 	P[i + 1] = P[i] << 1;
	// }
	// long long ans = 0;
	// for (int bit = 0 ; bit < (1 << N) ; bit++) {
	// 	bool ok = true;
	// 	std::vector R(N, false);
	// 	std::vector id(N, -1);
	// 	int cnt = 0;
	// 	for (int i = 0 ; i < N ; i++) {
	// 		if (bit & (1 << i)) {
	// 			R[i] = true;
	// 		}
	// 		else {
	// 			id[i] = cnt++;
	// 		}
	// 	}
	// 	for (int i = 0 ; i < M ; i++) {
	// 		ok &= !(R[A[i]] and R[B[i]]);
	// 	}
	// 	if (!ok) {
	// 		continue;
	// 	}
	// 	std::vector G(cnt, std::vector(0, 0));
	// 	for (int i = 0 ; i < M ; i++) {
	// 		if (!R[A[i]] and !R[B[i]]) {
	// 			G[id[A[i]]].push_back(id[B[i]]);
	// 			G[id[B[i]]].push_back(id[A[i]]);
	// 		}
	// 	}
	// 	if (zawa::bipartiteJudge(G).ok()) {
	// 		ans += P[zawa::connectedComponents(G).size()];
	// 	}
	// }
	// std::cout << ans << std::endl;

	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 199 - D RGB Coloring 2
 * https://atcoder.jp/contests/abc199/submissions/39401194
 */

#line 1 "test/ABC199-D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/graph/simple/bipartiteJudge.hpp"

#include <vector>
#include <stack>
#include <utility>

namespace zawa {

class bipartiteJudge {
private:
	std::vector<bool> colors;
	bool isBipartiteGraph;

	void build(const std::vector<std::vector<int>>& G) {
		if (G.empty()) {
			return;
		}
		std::stack<std::pair<int, bool>> S;
		std::vector<bool> used(G.size(), false);
		for (int i = 0 ; i < (int)G.size() ; i++) {
			if (!used[i]) {
				S.emplace(i, true);
				used[i] = true;
				colors[i] = true;
				while (S.size()) {
					auto [v, col] = S.top();
					S.pop();
					for (const auto& x : G[v]) {
						if (used[x]) {
							isBipartiteGraph &= colors[x] != col;
						}
						else {
							used[x] = true;
							colors[x] = !col;
							S.emplace(x, !col);
						}
					}
				}
			}
		}
	}

public:
	
	bipartiteJudge(const std::vector<std::vector<int>>& G) : colors(G.size()), isBipartiteGraph(true) {
		build(G);
	}

	template <class cost_type>
	bipartiteJudge(const std::vector<std::vector<std::pair<int, cost_type>>>& G) : colors(G.size()), isBipartiteGraph(true) {
		std::vector tmpG(G.size(), std::vector(0, 0));
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			for (const auto& [x, _] : G[i]) {
				tmpG[i].push_back(x);
			}
		}
		build(tmpG);
	}

	inline const bool ok() const {
		return isBipartiteGraph;
	}

	inline bool operator[](int i) const {
		return colors[i];
	}
};

} // namespace zawa
#line 2 "src/graph/simple/connectedComponents.hpp"

#line 5 "src/graph/simple/connectedComponents.hpp"

namespace zawa {

class connectedComponents {
private:
	std::vector<int> ids;
	std::vector<std::vector<int>> groups;    

	void build(const std::vector<std::vector<int>>& G) {
		int id = 0;
		for (int i = 0 ; i < (int)G.size() ; i++) {
			if (ids[i] == -1) {
				ids[i] = id;
				std::stack<int> stk({ i });		
				while (stk.size()) {
					int v = stk.top();
					stk.pop();
					for (auto x : G[v]) {
						if (ids[x] == -1) {
							ids[x] = id;
							stk.push(x);
						}
					}
				}
				id++;
			}
		}
		groups = std::vector(id, std::vector(0, 0));
		for (int i = 0 ; i < (int)ids.size() ; i++) {
			groups[ids[i]].push_back(i);
		}
	}

public:

	connectedComponents(const std::vector<std::vector<int>>& G) : ids(G.size(), -1) {
		build(G);
	}

	template <class cost_type>
	connectedComponents(const std::vector<std::vector<std::pair<int, cost_type>>>& G) : ids(G.size(), -1) {
		std::vector tmpG(G.size(), std::vector(0, 0));
		for (int i = 0 ; i < (int)G.size() ; i++) {
			for (auto [x, _] : G[i]) {
				tmpG[i].push_back(x);
			}
		}
		build(tmpG);
	}

	inline int operator [](int i) const {
		return ids[i];
	}

	inline std::size_t size() const {
		return groups.size();
	}

	inline std::size_t size(int x) const {
		return groups[ids[x]].size();
	}

	inline std::vector<std::vector<int>> comps() const {
		return groups;
	}

	inline std::vector<int> comp(int id) const {
		return groups[id];
	}

	bool same(int i, int j) const {
		return ids[i] == ids[j];
	}
};

} // namespace zawa
#line 5 "test/ABC199-D.test.cpp"

#include <iostream>

int main() {
	// int N, M; std::cin >> N >> M;
	// std::vector A(M, 0), B(M, 0);
	// for (int i = 0 ; i < M ; i++) {
	// 	std::cin >> A[i] >> B[i];
	// 	A[i]--; B[i]--;
	// }
	// std::vector P(N + 1, 1LL);
	// for (int i = 0 ; i < N ; i++) {
	// 	P[i + 1] = P[i] << 1;
	// }
	// long long ans = 0;
	// for (int bit = 0 ; bit < (1 << N) ; bit++) {
	// 	bool ok = true;
	// 	std::vector R(N, false);
	// 	std::vector id(N, -1);
	// 	int cnt = 0;
	// 	for (int i = 0 ; i < N ; i++) {
	// 		if (bit & (1 << i)) {
	// 			R[i] = true;
	// 		}
	// 		else {
	// 			id[i] = cnt++;
	// 		}
	// 	}
	// 	for (int i = 0 ; i < M ; i++) {
	// 		ok &= !(R[A[i]] and R[B[i]]);
	// 	}
	// 	if (!ok) {
	// 		continue;
	// 	}
	// 	std::vector G(cnt, std::vector(0, 0));
	// 	for (int i = 0 ; i < M ; i++) {
	// 		if (!R[A[i]] and !R[B[i]]) {
	// 			G[id[A[i]]].push_back(id[B[i]]);
	// 			G[id[B[i]]].push_back(id[A[i]]);
	// 		}
	// 	}
	// 	if (zawa::bipartiteJudge(G).ok()) {
	// 		ans += P[zawa::connectedComponents(G).size()];
	// 	}
	// }
	// std::cout << ans << std::endl;

	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 199 - D RGB Coloring 2
 * https://atcoder.jp/contests/abc199/submissions/39401194
 */

Back to top page