competitive_programming/Code Forces/Learning Languages/Learning Languages V1.cpp at master · ignaciohermosillacornejo/competitive_programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*
Problem: https://codeforces.com/problemset/problem/277/A
Tags: Graph, UnionFind
Status: Accepted
*/

#include <bits/stdc++.h>
using namespace std;
#define debugx(x) cerr << #x << ": " << x << endl
#define rep(i, n) for (int i = 0; i < n; ++i)
#define repx(i, x, n) for (int i = x; i < n; ++i)
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> par;
typedef vector<par> vp;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> graph;
typedef vector<vector<par>> wgraph;
typedef vector<par> vpar;

class UnionFind
{
  private:
    vi p, rank, setSize;
    int numSets;

  public:
    UnionFind(int N)
    {
        setSize.assign(N, 1);
        numSets = N;
        rank.assign(N, 0);
        p.assign(N, 0);
        for (int i = 0; i < N; i++)
            p[i] = i;
    }
    int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
    bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
    void unionSet(int i, int j)
    {
        if (!isSameSet(i, j))
        {
            numSets--;
            int x = findSet(i), y = findSet(j);
            // rank is used to keep the tree short
            if (rank[x] > rank[y])
            {
                p[y] = x;
                setSize[x] += setSize[y];
            }
            else
            {
                p[x] = y;
                setSize[y] += setSize[x];
                if (rank[x] == rank[y])
                    rank[y]++;
            }
        }
    }
    int numDisjointSets() { return numSets; }
    int sizeOfSet(int i) { return setSize[findSet(i)]; }
};

int main()
{
    int n, m;
    cin >> n >> m;
    vi lang(m, 0);
    int iliterate = 0;
    UnionFind u(m);
    rep(i, n)
    {
        int k;
        cin >> k;
        if (k == 0)
        {
            iliterate++;
            continue;
        }
        int a;
        cin >> a;
        a--;
        int last = a;
        lang[a] = 1;
        rep(j, k - 1)
        {
            cin >> a;
            a--;
            lang[a] = 1;
            u.unionSet(last, a);
        }
    }
    int rest = 0;
    rep(i, m)
    {
        if (lang[i] == 0)
            rest++;
    }
    cout << u.numDisjointSets() + iliterate - rest - (iliterate != n) << endl;
}