Submission #1070183

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i=0; i < int(n); i++)

int m;

// 素集合データ構造
struct UnionFind
{
	// par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
	vector<int> par;
	// sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
	vector<int> sizes;

	UnionFind(int n) : par(n), sizes(n, 1) {
		// 最初は全てのデータiがグループiに存在するものとして初期化
		rep(i, n) par[i] = i;
	}

	// データxが属する木の根を得る
	int find(int x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
	}

	// 2つのデータx, yが属する木をマージする
	void unite(int x, int y) {
		// データの根ノードを得る
		x = find(x);
		y = find(y);

		// 既に同じ木に属しているならマージしない
		if (x == y) return;

		// xの木がyの木より大きくなるようにする
		if (sizes[x] < sizes[y]) swap(x, y);

		// xがyの親になるように連結する
		par[y] = x;
		sizes[x] += sizes[y];
		// sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい
	}

	// 2つのデータx, yが属する木が同じならtrueを返す
	bool same(int x, int y) {
		return find(x) == find(y);
	}

	// データxが含まれる木の大きさを返す
	int size(int x) {
		return sizes[find(x)];
	}
};


// 頂点a, bをつなぐコストcostの（無向）辺
struct Edge
{
	int a, b, cost;

	// コストの大小で順序定義
	bool operator<(const Edge& o) const {
		return cost < o.cost;
	}
};

// 頂点数と辺集合の組として定義したグラフ
struct Graph
{
	int n;  // 頂点数
	vector<Edge> es;  // 辺集合

					  // クラスカル法で無向最小全域木のコストの和を計算する
					  // グラフが非連結のときは最小全域森のコストの和となる
	int kruskal() {
		// コストが小さい順にソート
		sort(es.begin(), es.end());

		UnionFind uf(n);
		int cnt = 0;

		rep(ei, es.size()) {
			Edge& e = es[ei];
			if (!uf.same(e.a, e.b)) {
				// 辺を追加しても閉路ができないなら、その辺を採用する
				cnt++;
				uf.unite(e.a, e.b);
			}
		}
		return m - cnt;
	}
};

// 標準入力からグラフを読み込む
Graph input_graph() {
	Graph g;
	cin >> g.n >> m;
	rep(i, m) {
		Edge e;
		cin >> e.a >> e.b >> e.cost;
		e.a--; e.b--;
		g.es.push_back(e);
	}
	return g;
}


int main()
{
	Graph g = input_graph();
	cout << g.kruskal() << endl;
	return 0;
}

Submission Info

Judge Result