test/connectedComponents1.test.cpp

• View this file on GitHub
• Last update: 2023-02-15 00:30:59+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_D

Depends on

• connectedComponents (連結成分分解 simple ver) (src/graph/simple/connectedComponents.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_D"

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

#include <cassert>
#include <vector>
#include <iostream>

int main() {
    int n, m; std::cin >> n >> m;
    std::vector G1(n, std::vector(0, 0));
    std::vector G2(n, std::vector(0, std::pair(0, 0)));
    for (int _ = 0 ; _ < m ; _++) {
        int s, t; std::cin >> s >> t;
        G1[s].push_back(t);
        G1[t].push_back(s);
        G2[s].emplace_back(t, 0);
        G2[t].emplace_back(s, 0);
    }
    zawa::connectedComponents cc1(G1);
	zawa::connectedComponents cc2(G2);
    int q; std::cin >> q;
    for (int _ = 0 ; _ < q ; _++) {
        int s, t; std::cin >> s >> t;
        assert(cc1.same(s, t) == cc2.same(s, t));
        assert(cc1.same(s, t) == (cc1[s] == cc1[t]));
        assert(cc2.same(s, t) == (cc2[s] == cc2[t]));
        std::cout << (cc1.same(s, t) ? "yes" : "no") << std::endl;
    }
}

#line 1 "test/connectedComponents1.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/11/ALDS1_11_D"

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

#include <vector>
#include <stack>

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 4 "test/connectedComponents1.test.cpp"

#include <cassert>
#line 7 "test/connectedComponents1.test.cpp"
#include <iostream>

int main() {
    int n, m; std::cin >> n >> m;
    std::vector G1(n, std::vector(0, 0));
    std::vector G2(n, std::vector(0, std::pair(0, 0)));
    for (int _ = 0 ; _ < m ; _++) {
        int s, t; std::cin >> s >> t;
        G1[s].push_back(t);
        G1[t].push_back(s);
        G2[s].emplace_back(t, 0);
        G2[t].emplace_back(s, 0);
    }
    zawa::connectedComponents cc1(G1);
	zawa::connectedComponents cc2(G2);
    int q; std::cin >> q;
    for (int _ = 0 ; _ < q ; _++) {
        int s, t; std::cin >> s >> t;
        assert(cc1.same(s, t) == cc2.same(s, t));
        assert(cc1.same(s, t) == (cc1[s] == cc1[t]));
        assert(cc2.same(s, t) == (cc2[s] == cc2[t]));
        std::cout << (cc1.same(s, t) ? "yes" : "no") << std::endl;
    }
}

Back to top page