fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1115;
  5. const int MAXM = 5115;
  6.  
  7.  
  8. int N, M, cnt = 0;
  9. int dl[MAXN];
  10.  
  11. struct Dosu {
  12.     int par[MAXN], sz[MAXN], cnt = 0;
  13.     void INIT() {
  14.         for (int i = 1; i <= N; i++) {
  15.             par[i] = i;
  16.             sz[i] = 1;
  17.         }
  18.     }
  19.  
  20.     int find_set(int u) {
  21.         return (par[u] == u ? u : par[u] = find_set(par[u]));
  22.     }
  23.  
  24.     void union_set(int u, int v) {
  25.         u = find_set(u), v = find_set(v);
  26.         if (sz[u] < sz[v]) swap(u, v);
  27.         par[v] = par[u];
  28.         sz[u] += sz[v];
  29.     }
  30.  
  31.     int solve() {
  32.         set<int> tmp;
  33.         for (int i = 1; i <= N; i++) tmp.insert(find_set(i));
  34.         return (int) tmp.size();
  35.     }
  36. } DSU;
  37.  
  38. main() {
  39.     ios_base::sync_with_stdio(0);
  40.     cin.tie(0);
  41.  
  42.     cin >> N >> M;
  43.  
  44.     DSU.INIT();
  45.  
  46.     while (M--) {
  47.         char c;
  48.         int a, b;
  49.         cin >> c >> a >> b;
  50.         if (c == 'F') DSU.union_set(a, b);
  51.         else {
  52.             int tmp = DSU.find_set(a);
  53.             if (dl[a] > 0) DSU.union_set(dl[a], b);
  54.             if (dl[b] > 0) DSU.union_set(a, dl[b]);
  55.             dl[a] = b;
  56.             dl[b] = a;
  57.         }
  58.     }
  59.  
  60.  
  61.     cout << DSU.solve();
  62. }
  63.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l8lkSU
language:
C++ (gcc 8.3)
created:
30 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!