Created
August 29, 2016 02:51
-
-
Save hamukichi/3f26c65133c977610dc751a3c93b6397 to your computer and use it in GitHub Desktop.
yukicoder No.416 旅行会社 に対するC++による解答コード。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <ciso646> | |
#include <cstdlib> | |
#include <iostream> | |
#include <numeric> | |
#include <set> | |
#include <vector> | |
#include <unordered_set> | |
#include <utility> | |
// グラフの辺を表すペア | |
typedef std::pair<int, int> Edge; | |
// 素集合データ構造、いわゆるUnion Find | |
class DisjointDataStructure { | |
public: | |
DisjointDataStructure(int number_of_nodes) { | |
// 各要素の親を格納する配列 | |
// 最初は自分自身が親である | |
par = std::vector<int>(number_of_nodes); | |
std::iota(par.begin(), par.end(), 0); | |
// 高さを格納する配列 | |
rank = std::vector<int>(number_of_nodes); | |
// 各要素を親とする集合の配列 | |
// 要素iが親でなければ空集合する | |
// 最初は、要素iが属する集合は{i} | |
// 追加した機能 | |
groups = std::vector<std::unordered_set<int>>(number_of_nodes); | |
for (int i = 0; i < number_of_nodes; i++) | |
{ | |
groups[i].insert(i); | |
} | |
} | |
// 要素nodeが含まれる木の根を求める | |
int root(int node) { | |
if (par[node] == node) | |
{ | |
return node; | |
} | |
else | |
{ | |
return par[node] = root(par[node]); | |
} | |
} | |
// 要素node1と要素node2は同じ集合に属しているか | |
inline bool inTheSameSet(int node1, int node2) { | |
return root(node1) == root(node2); | |
} | |
// 要素xが属する集合の要素を列挙する | |
// 追加した機能 | |
inline std::unordered_set<int> elementsOfGroup(int x) { | |
return groups[root(x)]; | |
} | |
// 要素node1とnode2の属する集合を合わせる | |
// unionは予約語なのでuniteとする | |
void unite(int node1, int node2) { | |
auto x = root(node1); | |
auto y = root(node2); | |
if (x != y) | |
{ | |
if (rank[x] < rank[y]) | |
{ | |
std::swap(x, y); | |
} | |
par[y] = x; | |
// 今回追加した機能 | |
// 子が属していた集合の中身を親の属している集合に全部入れる | |
// 子が属していた集合は空にする | |
groups[x].insert(groups[y].begin(), groups[y].end()); | |
groups[y].clear(); | |
if (rank[x] == rank[y]) | |
{ | |
rank[x]++; | |
} | |
} | |
} | |
private: | |
std::vector<int> par; | |
std::vector<int> rank; | |
std::vector<std::unordered_set<int>> groups; | |
}; | |
std::vector<int> solve(int n, int q, const std::set<Edge>& all_edges, | |
const std::vector<Edge>& removed_edges) { | |
auto removed_edges_set = std::set<Edge>(removed_edges.begin(), removed_edges.end()); | |
auto uf = DisjointDataStructure(n); | |
constexpr int root = 0; | |
// 答えを格納する配列 | |
// 0で初期化されている | |
// はじめに与えられたグラフで頂点iが0とつながらないときには、 | |
// 以下の処理の対象にならず、con_time[i] = 0のままである | |
auto con_time = std::vector<int>(n); | |
// 壊されない辺からなるグラフを考える | |
for (const auto& edge : all_edges) | |
{ | |
if (removed_edges_set.count(edge) == 0) | |
{ | |
uf.unite(edge.first, edge.second); | |
} | |
} | |
// この時点で0と同じ連結成分にある頂点は、 | |
// 辺が壊されてもなおそうである | |
for (int i = 1; i < n; i++) | |
{ | |
if (uf.inTheSameSet(root, i)) | |
{ | |
con_time[i] = -1; | |
} | |
} | |
// クエリを逆から処理し、壊されない辺からなるグラフに、 | |
// 辺が追加されていくと考える | |
for (int i = q - 1; i >= 0; i--) | |
{ | |
auto source = removed_edges[i].first; | |
auto dest = removed_edges[i].second; | |
// 辺の始終点がはじめから同じ連結成分にあれば、 | |
// わざわざuniteしなくてもよい | |
// さもなければ、以下の処理を行う | |
if (not uf.inTheSameSet(source, dest)) | |
{ | |
// 長ったらしいので変数に入れておく | |
auto bs = uf.inTheSameSet(root, source); | |
auto bd = uf.inTheSameSet(root, dest); | |
// 辺の追加前に、辺の始終点がともに0と同じ連結成分になければ、 | |
// 単純にuniteすればよい | |
// さもなければ、以下の処理を行ってからuniteする | |
if (bs or bd) | |
{ | |
// ややこしいので、始点が0と同じ連結成分にあり、 | |
// 終点はそうではないという場合に統一する | |
// なお、ともに0と同じ連結成分にある場合は、 | |
// 当然ながら上の条件分岐で除外されている | |
if (bd) | |
{ | |
std::swap(source, dest); | |
} | |
// 辺の追加前に終点が属する集合を構成する頂点は、 | |
// 辺の追加により0とつながる | |
for (const auto& v : uf.elementsOfGroup(dest)) | |
{ | |
con_time[v] = i + 1; | |
} | |
} | |
uf.unite(source, dest); | |
} | |
} | |
return con_time; | |
} | |
int main() { | |
std::cin.tie(nullptr); | |
std::ios::sync_with_stdio(false); | |
int n, m, q; | |
std::cin >> n >> m >> q; | |
// すべての辺の集合 | |
// ペアのハッシュを定義するのが面倒なので、 | |
// std::unordered_setではなくset::setを使っている | |
std::set<Edge> all_edges; | |
for (int i = 0; i < m; i++) | |
{ | |
int a, b; | |
std::cin >> a >> b; | |
a--; | |
b--; | |
all_edges.insert(std::make_pair(a, b)); | |
} | |
// 壊される辺の配列 | |
// 壊される順番が大事なので、集合にはしない | |
std::vector<Edge> removed_edges; | |
for (int i = 0; i < q; i++) | |
{ | |
int c, d; | |
std::cin >> c >> d; | |
c--; | |
d--; | |
removed_edges.push_back(std::make_pair(c, d)); | |
} | |
auto con_time = solve(n, q, all_edges, removed_edges); | |
for (int i = 1; i < n; i++) | |
{ | |
std::cout << con_time[i] << std::endl; | |
} | |
return EXIT_SUCCESS; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment