2269. Компоненты связности
Задан неориентированный невзвешенный граф. Найдите количество
его компонент связности.
Вход. В первой строке содержится количество вершин n (n
≤ 100) в графе. Далее в n
строках задается по n чисел – матрица
смежности графа: в i-ой строке
на j-ом месте стоит 1, если вершины i и j
соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы
стоят нули. Матрица симметрична относительно главной диагонали.
Выход. Выведите
количество компонент связности графа.
|
Пример
входа |
Пример
выхода |
60 1 1 0 0 01 0 1 0 0 01 1 0 0 0 00 0 0 0 1 00 0 0 1 0 0
0 0 0 0 0 0 |
3 |
РЕШЕНИЕ
графы –
компоненты связности
Анализ алгоритма
Используя
систему непересекающихся множеств, ищем количество компонент связности в графе.
Изначально расположим каждую вершину в отдельном
множестве. Каждая вершина является представителем своего множества.
Далее
для каждого ребра (u, v) объединим множества, содержащие u и v. После
обработки всех ребер количество компонент связности равно числу множеств в системе
непересекающихся множеств.
Задачу можно
решить также при помощи поиска в глубину. Количество вызовов функции dfs будет равно числу
компонент связности графа.
Пример
Приведенный в примере граф имеет вид:
Изначально расположим каждую вершину в отдельном
множестве. Каждая вершина является представителем своего множества.
Далее
для каждого ребра (u, v) объединим множества, содержащие u и v. После
обработки всех ребер две вершины будут находиться в одной компоненте связности
если у них одинаковый представитель.
Количество
компонент связности равно числу множеств в системе непересекающихся множеств.
Количество множеств равно числу представителей, а именно количеству таких v,
для которых parent[v] = v. В примере имеется три
представителя: 3, 5 и 6. То есть в графе имеется три компоненты связности.
Реализация алгоритма
В MAX содержится
максимальное количество вершин в графе. В mas[i] содержится номер
вершины, на которую указывает вершина i.
#define MAX 102
int mas[MAX];
Функция Repr
возвращает номер вершины – представителя множества, содержащего вершину n.
Двигаемся по указателю на следующий элемент, пока не встретим представителя
множества (его указатель указывает на него самого).
int Repr(int
n)
{
while (n !=
mas[n]) n = mas[n];
return
n;
}
Функция Union
объединяет два множества, которые содержат вершины x и y. Ищем
представителей множеств, содержащих x и y. Пусть этими
представителями будут x1 и y1. Если x1
= y1, то x и y содержатся в одном множестве, и
в таком случае ничего делать не надо. Иначе указатель представителя x1
перенаправляем на y1.
void Union(int
x,int y)
{
int x1 =
Repr(x),y1 = Repr(y);
if (x1 == y1)
return;
mas[x1] = y1;
}
Основная часть программы. Изначально каждая вершина
указывает сама на себя (mas[i] = i).
scanf("%d",&n);
for(i = 1; i <= n; i++) mas[i] = i;
Читаем матрицу смежности. Для каждого ребра (i, j),
где i < j, совершаем объединение множеств, содержащих вершины i и j.
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
scanf("%d",&value);
if (i > j)
continue;
if (value)
Union(i,j);
}
Подсчитываем количество компонент
связности в переменной count. Оно
равно количеству вершин – представителей множеств (которые указывают сами на
себя).
for(i = 1; i <= n; i++)
if (mas[i] ==
i) count++;
Выводим ответ.
printf("%d\n",count);
Реализация
алгоритма – поиск
в глубину
#include <stdio.h>
#include <string.h>
#define MAX 102
int n, i, j, res;
int g[MAX][MAX], used[MAX];
void dfs(int v)
{
used[v] = 1;
for(int
i = 0; i < n; i++)
if (g[v][i] && !used[i]) dfs(i);
}
int main(void)
{
scanf("%d",&n);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d",&g[i][j]);
memset(used,0,sizeof(used));
res = 0;
for(i = 0; i < n; i++)
if
(!used[i])
{
dfs(i);
res++;
}
printf("%d\n",res);
return 0;
}
Java реализация – dfs
import java.util.*;
public class Main
{
static int g[][],
used[];
static int n;
static void dfs(int v)
{
used[v] =
1;
for(int i = 1;
i <= n; i++)
if (g[v][i] ==
1 && used[i] ==
0) dfs(i);
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
n = con.nextInt();
g = new int[n+1][n+1];
used = new int[n+1];
for(int i = 1;
i <= n; i++)
for(int j = 1;
j <= n; j++)
g[i][j] = con.nextInt();;
int res = 0;
for(int i = 1;
i <= n; i++)
if (used[i] ==
0)
{
dfs(i);
res++;
}
System.out.println(res);
con.close();
}
}
Java реализация – dsu
import java.util.*;
public class Main
{
static int mas[];
static int n;
static int
Repr(int n)
{
while (n != mas[n]) n = mas[n];
return n;
}
static void
Union(int x,int y)
{
int x1 = Repr(x);
int y1 = Repr(y);
if (x1 == y1) return;
mas[x1] = y1;
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
n = con.nextInt();
mas = new int[n+1];
for(int i = 1;
i <= n; i++) mas[i] = i;
for(int i = 1;
i <= n; i++)
for(int j = 1;
j <= n; j++)
{
int val = con.nextInt();
if (i >
j) continue;
if (val ==
1) Union(i,j);
}
int count = 0;
for(int i = 1;
i <= n; i++)
if (mas[i] == i) count++;
System.out.println(count);
con.close();
}
}
Python реализация – dsu
def Repr(n):
while (n !=
mas[n]): n = mas[n]
return n
def Union(x, y):
x1
= Repr(x)
y1
= Repr(y)
if (x1 == y1): return
mas[x1] = y1
n = int(input())
mas = [int(i) for i in range (n+1)]
for i in range(1,n+1):
lst = [0] + [int(j) for j in input().split()]
for j in range(1, n + 1):
if (i < j and lst[j] == 1): Union(i, j)
res = 0
for i in range(1, n+1):
if (mas[i] == i):
res += 1
print(res)
Python реализация – dfs
MAX = 102
n = int(input())
g = [[0] * MAX for _ in range(MAX)]
used = [0] * MAX
res = 0
def dfs(v):
used[v] = 1
for
i in range(n):
if
g[v][i] and not used[i]:
dfs(i)
for i in
range(n):
row = list(map(int, input().split()))
for
j in range(n):
g[i][j] = row[j]
for i in
range(n):
if
not used[i]:
dfs(i)
res += 1
print(res)