Official

D - Friends Editorial by evima


First, you have to realize that, if there are a path from one person to another along the friendship relationships, then those two people are friends. Assume that there are five people, \(A, B, C, D\) and \(E\), and there are four pairs of friendship relationships, \((A, B), (B, C), (C, D)\) and \((D, E)\). Here, from the viewpoint of \(A\), if \(B\) is a friend, then \(C\) is a friend too, and if \(C\) is a friend, \(D\) is also a friend, …and so on, and this chain makes all the people friends. Of course, other people than \(A\) can also be friends of all other people.

Summarizing, all the people who are connected with friendship relationships are friends with each other, and those who are not connected are not friends with each other. Rather than managing them with graphs, it is better to manage them with sets.

For example, in Sample 1, there are three friendship relationships, \((1, 2)\), \((3, 4)\) and \((5, 1)\). This is equivalent to friendships represented by two sets, \((1, 2, 5)\) and \((3, 4)\), in which any two people from the same set are friends with each other. (We will call them as “friends-sets”)

Now let us return to the problem. If a pair of people from the same friends-set are placed to the same group, they will be friends with each other, so the conditions cannot be satisfied. Therefore, they should be divided into at least \(K\) groups, where \(K\) denotes the maximum number of members in each friends-set.

Now, if we prove that we can always divide into \(K\) groups, then the answer will be \(K\). This distribution can be achieved by a simple algorithm in fact For each friends-set, just distribute its member one by one from group 1. With this simple algorithm, there will be at most one member from the same friends-set in every group, so we can achieve the situation where friends are in the same group. Therefore, we now see that we can solve this problem by find the friends-sets and count the maximum number of members.

To manage the friends-set, it can be solved by using disjoint-set data structure called Union-Find. Even if you do not know Union-Find, you can still solve the problem in the similar way by applying Breadth-First Search (BFS) algorithms to inspect connected components.

Sample Code(C++, A solution using Union-Find)

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

struct UnionFind {
	//If the vertex is a parent, this value will be the number of vertices that belongs to the set, multiplied by -1
	//Otherwise, this value will be the parent's 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;
	
	//Make friends-sets
	UnionFind UF(N);
	for (int i = 0; i < M; i++)
	{
		int A, B;
		cin >> A >> B;
		A -= 1; B -= 1;
		UF.unite(A, B);
	}

	//Find the maximum friends-set
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		ans = max(ans, UF.size(i));
	}

	cout << ans << endl;
}

posted:
last update: