CSES. Road Reparation

1.Problem

https://cses.fi/problemset/task/1675

2.Idea

Standard MST with UnionFind implementation

3.Source

 int n, m;  
 struct Edge {  
      int u, v, c;  
      bool operator < (const Edge &a)const {  
           return c < a.c;  
      }  
 } Edges[N];  
 struct UF {  
      vector<int> Parent;  
      vector<int> Size;  
      int Count;  
      void init(int n) {  
           Count = n;  
           Parent.resize(n);  
           Size.resize(n);  
           REP(i, n) {  
                make_set(i);  
           }  
      }  
      void make_set(int v) {  
           Parent[v] = v;  
           Size[v] = 1;  
      }  
      int find_set(int v) {  
           if (v == Parent[v])  
                return v;  
           return Parent[v] = find_set(Parent[v]);  
      }  
      void union_sets(int a, int b) {  
           a = find_set(a);  
           b = find_set(b);  
           if (a != b) {  
                if (Size[a] < Size[b])  
                     swap(a, b);  
                Count--;  
                Parent[b] = a;  
                Size[a] += Size[b];  
           }  
      }  
 };  
 void solve()  
 {  
      cin >> n >> m;  
      REP(i, m) {  
           cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;  
           Edges[i].u--;  
           Edges[i].v--;  
      }  
      sort(Edges, Edges + m);  
      UF uf;  
      uf.init(n);  
      Int ret = 0;  
      REP(i, m) {  
           int u = Edges[i].u;  
           int v = Edges[i].v;  
           int c = Edges[i].c;  
           if (uf.find_set(u) != uf.find_set(v)) {  
                ret += c;  
                uf.union_sets(u, v);  
           }  
      }  
      if (uf.Count == 1) cout << ret << endl;  
      else cout << "IMPOSSIBLE" << endl;  
 }  

ARC106 B - Values

Problem:

B - Values (atcoder.jp)

Idea:

Check sum of nodes in the same connected components

Source:

int n, m;
Int a[N], b[N];

struct UF {
	vector<int> Parent;
	vector<int> Size;
	void init(int n) {
		Parent.resize(n);
		Size.resize(n);
		REP(i, n) {
			make_set(i);
		}
	}
	void make_set(int v) {
		Parent[v] = v;
		Size[v] = 1;
	}
	int find_set(int v) {
		if (v == Parent[v])
			return v;
		return Parent[v] = find_set(Parent[v]);
	}
	void union_sets(int a, int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (Size[a] < Size[b])
				swap(a, b);
			Parent[b] = a;
			Size[a] += Size[b];
		}
	}
};

void solve()
{
	cin >> n >> m;
	REP(i, n) cin >> a[i];
	REP(i, n) cin >> b[i];

	UF uf;
	uf.init(n);
	REP(i, m) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		uf.union_sets(u, v);
	}
	map<int, Int> mp1, mp2;
	REP(i, n) {
		int par = uf.find_set(i);
		mp1[par] += a[i];
		mp2[par] += b[i];
	}

	for (auto x : mp1) {
		int par = x.first;
		if (mp1[par] != mp2[par]) {
			cout << "No" << endl;
			return;
		}
	}
	cout << "Yes" << endl;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(9);
	solve();
	return 0;
}