ABC126 E 1 or 2 グラフに見えるか？？

ABC126 E 1 or 2

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc126/tasks/abc126_e

考察

• かのどちらかが分かればもう片方も分かることに気がついた
• これをグラフの連結成分になっていると見ると，答えが連結成分の個数だということが見えてきた
• 連結成分の個数はUnion-Findを使って実装すればよいので実装する
• サンプルも優しくて解きやすい感じ
• Union-Findのライブラリを改修したい（切実）

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };




/******************************************************************************************/


//繋げる方向を一方向にする
typedef struct union_find{
    
    vector<int> pa;//親
    vector<int> ra;//木の深さ
    vector<int> siz;
    //n要素で初期化
    void init(int n){
        pa.resize(n);
        ra.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++){
            pa[i] = i;/*各ノードに番号を振る,この時par[x]=xとなる時は木の根となる*/
            ra[i] = 0LL;/*各ノード自体の高さは0*/
            siz[i] = 1LL;
        }
    }
    //木の根を求める
    int find(int x){
        if(pa[x] == x){
            return x;/*根ならそのノードの番号を返す*/
        }else{
            return pa[x] = find(pa[x]);/*根でないならさらにノードの根を探す*/
        }
    }

    //xとyの属する集合を併合する
    void unite(int x,int y){
        x = find(x);//xの根の番号を探す
        y = find(y);//yの根の番号を探す
        if(x == y){//一致すればつながっている
            return;
        }
        pa[y] = x;
        siz[x] += siz[y];
    }

    //xとyが同じ集合に属するか判定
    bool same(int x,int y){
        return find(x) == find(y);//同じ集合なら1、違うなら0が返る
    }
}UF;



int main(){

	int n, m;
	cin >> n >> m;
	int ans = 0;

	vector<int> x(m), y(m), z(m);
	UF tree;
	tree.init(n + 10);
	
	for (int i = 0; i < m; i++){
		cin >> x[i] >> y[i] >> z[i];
		x[i]--;
		y[i]--;
		tree.unite(x[i], y[i]);
	}

	set<int> st;
	for (int i = 0; i < n; i++)
	{
		st.insert(tree.find(i));
	}
	cout << st.size() << endl;


	return 0;
}