結果

問題 No.330 Eigenvalue Decomposition
コンテスト
ユーザー koyumeishi
提出日時 2015-12-23 13:06:39
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 75 ms / 5,000 ms
コード長 1,658 bytes
コンパイル時間 829 ms
コンパイル使用メモリ 96,904 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2024-09-18 21:43:37
合計ジャッジ時間 2,629 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |                 scanf("%lld%lld%lld", &a[i],&b[i],&c[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
using namespace std;
template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<class T> istream& operator , (istream& is, T& val){ return is >> val;}
template<class T> ostream& operator << (ostream& os, vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"\n":" ");return os;}

class UnionFindTree{
	typedef struct {
		int parent;
		int rank;
	}base_node;
	
	vector<base_node> node;
public:
	UnionFindTree(int n){
		node.resize(n);
		for(int i=0; i<n; i++){
			node[i].parent=i;
			node[i].rank=0;
		}
	}

	int find(int x){
		if(node[x].parent == x) return x;
		else{
			return node[x].parent = find(node[x].parent);
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}

	void unite(int x, int y){
		x = find(node[x].parent);
		y = find(node[y].parent);
		if(x==y) return;
		if(node[x].rank < node[y].rank){
			node[x].parent = y;
		}else if(node[x].rank > node[y].rank){
			node[y].parent = x;
		}else{
			node[x].rank++;
			unite(x,y);
		}
	}
};

int main(){
	int n,m;
	cin >> n >> m;

	vector<long long> a(m),b(m),c(m);
	UnionFindTree uft(n);
	for(int i=0; i<m; i++){
		scanf("%lld%lld%lld", &a[i],&b[i],&c[i]);
		a[i]--; b[i]--;
		uft.unite(a[i], b[i]);
	}
	vector<int> root(n,0);
	for(int i=0; i<n; i++){
		root[uft.find(i)] = 1;
	}
	int ans = count(root.begin(), root.end(), 1);

	cout << ans << endl;
	return 0;
}
0