結果
問題 | No.330 Eigenvalue Decomposition |
ユーザー |
|
提出日時 | 2017-11-09 22:27:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 5,000 ms |
コード長 | 1,664 bytes |
コンパイル時間 | 1,415 ms |
コンパイル使用メモリ | 171,484 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-24 07:34:17 |
合計ジャッジ時間 | 4,252 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;class DisjointSets{public:DisjointSets(const int v){m_parent.resize(v);m_rank.resize(v);m_size.resize(v);for (int i = 0; i < v; i++) {m_parent[i] = i;m_rank[i] = 0;m_size[i] = 1;}}bool same(const int a, const int b){return find(a) == find(b);}int find(const int a){if (m_parent[a] == a) {return a;} else {return m_parent[a] = find(m_parent[a]);}}void unite(const int a_, const int b_){const int a = find(a_);const int b = find(b_);if (a == b) {return;}if (m_rank[a] > m_rank[b]) {m_parent[b] = a;m_size[a] += m_size[b];} else {m_parent[a] = b;m_size[b] += m_size[a];}if (m_rank[a] == m_rank[b]) {m_rank[b]++;}}int getSize(const int a){return m_size[m_parent[a]];}private:vector<int> m_parent;vector<int> m_rank;vector<int> m_size;};int main(){cin.tie(0);ios::sync_with_stdio(false);int N, M;cin >> N >> M;DisjointSets uf(N);for (int i = 0; i < M; i++) {int a, b, c;cin >> a >> b >> c;a--, b--;uf.unite(a, b);}vector<int> num(N, 0);for (int i = 0; i < N; i++) {num[uf.find(i)] = 1;}const int cnt = accumulate(num.begin(), num.end(), 0);cout << cnt << endl;return 0;}