Union-Find の典型的な問題！！
でも、DFS や BFS でも解くことができる。

問題概要

人 $1$ から人 $N$ までの $N$ 人の人がいます。

「人 $A_{i}$ と人 $B_{i}$ は友達である」という情報が $M$ 個与えられます。同じ情報が複数回与えられることもあります。

$X$ と $Y$ が友達、かつ、 $Y$ と $Z$ が友達ならば、 $X$ と $Z$ も友達です。また、 $M$ 個の情報から導くことができない友達関係は存在しません。

わるい高橋君は、この $N$ 人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。

最小でいくつのグループに分ければ良いでしょうか？

制約

$N, M \le 2 \times 10^{5}$

考えたこと

少し状況がわかりにくいかもしれない。こういうのはわかりやすく言い換えていくことが大切になる。人と人との $M$ 個の関係性を整理すると、下図のようにグラフで表すことができる。そしてグラフは、何個かの「連結成分」に分けることができる (下図では 3 個)。

このとき、最大サイズの連結成分のサイズを $m$ とする (上図では $m = 9$ ) と、「同じグループの中に友達がいない」という状況を作るためには、少なくとも $m$ 個のグループが必要であることがわかる。

逆に $m$ 個のグループがあれば、同一連結成分の人々をすべてバラバラにすることができる。

以上より、次の問題に帰着されることがわかった！

$N$ 頂点、 $M$ 辺の無向グラフが与えられる。グラフの連結成分のうち、サイズが最大であるもののサイズを求めよ。

解法 (1)：Union-Find

Union-Find を用いることで、連結成分を効率よく管理できる。ここでは union by size による実装を示す。union by size を用いると、「各連結成分のサイズ」も自然に取得できる！

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        uf.merge(a, b);
    }
    int res = 0;
    for (int i = 0; i < N; ++i) res = max(res, uf.size(i));
    cout << res << endl;
}

解法 (2)：DFS

DFS によってもグラフを各連結成分ごとに分解することができる。DFS とは、

グラフ上の一点 v を始点として
それに繋がる点を再帰的に呼び出していく

というものである。よって、各連結成分に対して、その中の 1 点 v に対して再帰関数 dfs(v) を呼び出すと、v を含む連結成分内の頂点をすべて訪問することになる。

このときの訪問数が「v を含む連結成分のサイズ」となる。その最大値を求めればよい。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

void dfs(const Graph &G, vector<bool> &seen, int v, int &cnt) {
    seen[v] = true;
    ++cnt;
    for (auto nv : G[v]) if (!seen[nv]) dfs(G, seen, nv, cnt);
}

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b), G[b].push_back(a);
    }
    int res = 0;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        int cnt = 0;
        dfs(G, seen, v, cnt);
        res = max(res, cnt);
    }
    cout << res << endl;
}

解法 (3)：BFS

DFS による解法とまったく同じ考え方で、BFS によっても解ける。

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

int bfs(const Graph &G, vector<int> &dist, int s) {
    int cnt = 0;
    dist[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        ++cnt;
        for (auto nv : G[v]) {
            if (dist[nv] == -1) {
                dist[nv] = dist[v] + 1;
                que.push(nv);
            }
        }
    }
    return cnt;
}

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b), G[b].push_back(a);
    }
    int res = 0;
    vector<int> dist(N, -1);
    for (int v = 0; v < N; ++v) {
        if (dist[v] != -1) continue;
        res = max(res, bfs(G, dist, v));
    }
    cout << res << endl;
}