10608. Друзья
В городе проживают n людей, некоторые из которых дружат друг с другом. Известно, что если A – друг B, а B – друг C, то A – друг C. Определить количество
людей в наибольшей группе друзей.
Вход.
Первая строка содержит количество тестов. Первая строка каждого теста содержит
количество людей в городе n (1 £ n £ 30000) и количество пар друзей m (0 £ m £ 500000). Каждая из следующих m строк содержит номера друзей a и b (1 £ a, b £
n, a ¹ b).
Выход. Для каждого теста вывести количество людей в наибольшей
группе друзей.
2
3
2
1
2
2
3
10
12
1
2
3
1
3
4
5
4
3
5
4
6
5
2
2
1
7
10
1
2
9
10
8
9
Пример выхода
36
графы, компоненты связности
Реализуем систему
непересекающихся множеств на основе леса деревьев. Пусть MAX – количество вершин в графе. Для каждого множества
вычисляем количество элементов в нем. Для этого заведем массив deg[MAX]. deg[i] будет содержать количество
элементов во множестве, в котором находится вершина i, если i – представитель множества, и deg[i] = 0 иначе. Остается вывести
максимальное значение в массиве deg.
Рассмотрим первый тест. Граф
состоит из 3 вершин, которые связаны друг с другом. Имеется одна группа людей,
которая содержит 3 друга.
Принцип построения системы
непересекающихся множеств на основе леса деревьев описан в статье «Компоненты
связности».
#define MAX 30001
int mas[MAX], deg[MAX];
Функция поиска представителя
элемента n.
int Repr(int
n)
{
while (n !=
mas[n]) n = mas[n];
return
n;
}
Объединение деревьев, содержащих
элементы x
и y.
void Union(int
x,int y)
{
int x1 =
Repr(x),y1 = Repr(y);
if (x1 == y1)
return;
mas[x1] = y1;
}
Основная часть программы.
Считываем входные данные, сразу строим систему непересекающихся множеств.
scanf("%d",&tests);
while (tests--)
{
scanf("%d
%d",&n,&m);
for(i = 0; i
< n; i++) mas[i] = i;
for(i = 0; i
< m; i++)
scanf("%d
%d",&a,&b), Union(a,b);
Обнуляем массив deg.
memset(deg,0,sizeof(deg));
Для каждой вершины i ищем ее представителя j и увеличиваем значение deg[j] на 1.
for(i = 0; i < n; i++)
deg[Repr(i)]++;
Ищем множество с наибольшим
количеством вершин.
for(res = i =
0; i < n; i++)
if (deg[i]
> res) res = deg[i];
printf("%d\n",res);
}