まず気付くべきなのは、友達関係を辿って辿り着ける人は友達であるということです。 \(A, B, C, D, E\) の5人がいたとして、\((A,B) , (B,C), (C,D), (D,E)\) の\(4\) ペアが友達だったとしましょう。この時、\(A\) 視点で考えて、 \(B\) が友達なら \(C\) も友達であり、\(C\) が友達なら \(D\)も友達であり……と連鎖して、全員が友達になっていきます。当然 \(A\) 以外も同様に、全ての人と友達になることが出来ます。

これを整理すると、友達関係が繋がっている人は全員が友達同士であり、繋がっていない人は友達同士ではない ということが言えます。これらを管理するのは、グラフではなく、集合で管理するのが良いでしょう。

例えばサンプル \(1\) においては、\((1,2), (3,4), (5,1)\) という\(3\) つの友達関係がありますが、これは \((1,2,5), (3,4)\) の、\(2\) つの友達関係で結ばれている集合に分けることが出来ます。（以下、これを友達集合と呼びます）

ここで問題に戻ります。同じ友達集合に所属する人同士を、同じグループに配置してしまうと、その人達は友達同士になってしまうため、条件を満たすことが出来ません。そこで、最も人数の多い友達集合の人数を \(K\) とすると、最低でも \(K\) グループに分ける必要があることがわかります。

これで、\(K\) グループに必ず分けられることが証明出来れば、答えが\(K\) となります。このグループ分けは、実は単純なアルゴリズムで実現することが出来ます。 各友達集合について、グループ \(1 \) から順番に \(1\) 人ずつ割り振っていくだけです。こうするだけで、同じ友達集合から各グループに割り振られる人はたかだか \(1\) 人となるため、友達同士が同じグループになることを避けることが出来ます。つまり、友達集合を求め、その最大人数を計算することで、この問題が解けることがわかりました。

友達集合を管理するには、Union-Findなどと呼ばれる素集合データ構造を使うことで、解くことが出来ます。もしUnion-Findを知らない場合も、幅優先探索などで連結成分を調べることで、同様に解くことが可能です。

回答例(C++, Union-Findを使った回答)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct UnionFind {
	//自身が親であれば、その集合に属する頂点数に-1を掛けたもの
	//そうでなければ親のid
	vector<int> r;

	UnionFind(int N) {
		r = vector<int>(N, -1);
	}

	int root(int x) {
		if (r[x] < 0) return x;
		return r[x] = root(r[x]);
	}

	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (r[x] > r[y]) swap(x, y);
		r[x] += r[y];
		r[y] = x;
		return true;
	}

	int size(int x) {
		return -r[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 -= 1; B -= 1;
		UF.unite(A, B);
	}

	//最大の友達集合を求める
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		ans = max(ans, UF.size(i));
	}

	cout << ans << endl;
}