982. Связность

 

Проверьте, является ли заданный неориентированный граф связным. То есть можно ли из любой вершины добраться до любой другой, используя рёбра графа.

 

Вход. В первой строке заданы два числа: n (1 ≤ n ≤ 100) – количество вершин и m (1 ≤ m ≤ 104) – количество ребер в графе. Каждая из следующих m строк содержит два числа ui и vi (1 ≤ ui, vi ≤ n), обозначающих ребро между вершинами ui и vi.

 

Выход. Выведите “YES”, если граф является связным, и “NO” – в противном случае.

 

Пример входа 1

Пример выхода 1

3 2

1 2

3 2

YES

 

 

Пример входа 2

Пример выхода 2

3 1

1 3

NO

 

 

РЕШЕНИЕ

поиск в глубину

 

Анализ алгоритма

При помощи поиска в глубину вычислим количество компонентов связности. Если оно равно 1, то граф является связным.

Второй вариант решения задачи – запустить поиск в глубину из вершины 1 и посчитать количество посещенных вершин. Если оно равно n, то граф является связным.

 

Пример

Графы, приведенные в примерах, имеют вид:

 

Реализация алгоритма

Объявим матрицу смежности g и массив посещенных вершин used.

 

#define MAX 101

int g[MAX][MAX], used[MAX];

 

Функция dfs совершает поиск в глубину из вершины v.

 

void dfs(int v)

{

  used[v] = 1;

  for (int i = 1; i <= n; i++)

    if (g[v][i] && !used[i]) dfs(i);

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d %d", &n, &m);

 

Инициализируем массивы.

 

memset(g,0,sizeof(g));

memset(used,0,sizeof(used));

 

Строим матрицу смежности графа.

 

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a][b] = g[b][a] = 1;

}

 

Количество компонент связности подсчитываем в переменной cnt.

 

cnt = 0;

 

Запускаем поиск в глубину на несвязном графе.

 

for (i = 1; i <= n; i++)

  if (!used[i])

  {

 

Количество вызовов функции dfs равно числу компонент связности графа.

 

    dfs(i);

    cnt++;

  }

 

Выводим ответ. Если граф содержит только одну компоненту связности, то он связный.

 

if (cnt == 1) printf("YES\n");

else printf("NO\n");

 

Реализация алгоритма – количество посещенных вершин

Объявим матрицу смежности g и массив посещенных вершин used.

 

#define MAX 101

int g[MAX][MAX], used[MAX];

 

Функция dfs совершает поиск в глубину из вершины v. В переменной cnt подсчитываем количество посещенных вершин.

 

void dfs(int v)

{

  used[v] = 1;

  cnt++;

  for (int i = 1; i <= n; i++)

    if ((g[v][i] == 1) && (used[i] == 0)) dfs(i);

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d %d", &n,&m);

 

Инициализируем массивы.

 

memset(g, 0, sizeof(g));

memset(used, 0, sizeof(used));

 

Строим матрицу смежности графа.

 

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a][b] = g[b][a] = 1;

}

 

Запускаем поиск в глубину из вершины 1.

 

cnt = 0;

dfs(1);

 

Если в результате поиска в глубину были посещены все n вершин, то граф связный.

 

if (cnt == n) printf("YES\n");

else printf("NO\n");

 

Реализация алгоритма – система непересекающихся множеств

Объявим рабочий массив.

 

#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;

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d %d", &n, &m);

 

Изначально каждая вершина указывает сама на себя (mas[i] = i).

 

for (i = 1; i <= n; i++) mas[i] = i;

 

Читаем ребра графа. Для каждого ребра (a, b) совершаем объединение множеств, содержащих вершины a и b.

 

for (i = 1; i <= m; i++)

{

  scanf("%d %d", &a, &b);

  Union(a, b);

}

 

Подсчитываем количество компонент связности в переменной count. Оно равно количеству вершин – представителей множеств (которые указывают сами на себя).

 

count = 0;

for (i = 1; i <= n; i++)

  if (mas[i] == i) count++;

 

В зависимости от значения переменной count выводим ответ.

 

if (count == 1) printf("YES\n");

else printf("NO\n");

 

Python реализация

Функция dfs совершает поиск в глубину из вершины v.

 

def dfs(v):

  used[v] = 1

  for i in range(1, n + 1):

    if g[v][i] and not used[i]:

      dfs(i)

 

Основная часть программы. Читаем входные данные.

 

n, m = map(int, input().split())

 

Инициализируем списки.

 

g = [[0] * (n + 1) for _ in range(n + 1)]

used = [0] * (n + 1)

 

Строим матрицу смежности графа.

 

for i in range(m):

  a, b = map(int, input().split())

  g[a][b] = g[b][a] = 1

 

Количество компонент связности подсчитываем в переменной cnt.

 

cnt = 0

 

Запускаем поиск в глубину на несвязном графе.

 

for i in range(1, n + 1):

  if not used[i]:

 

Количество вызовов функции dfs равно числу компонент связности графа.

 

    dfs(i)

    cnt += 1

 

Выводим ответ. Если граф содержит только одну компоненту связности, то он связный.

 

if cnt == 1:

  print("YES")

else:

  print("NO")

 

Python реализация алгоритма – количество посещенных вершин

Функция dfs совершает поиск в глубину из вершины v. В переменной cnt подсчитываем количество посещенных вершин.

 

def dfs(v):

  used[v] = 1

  global cnt

  cnt += 1

  for i in range(1, n + 1):

    if g[v][i] and not used[i]:

      dfs(i)

 

Основная часть программы. Читаем входные данные.

 

n, m = map(int, input().split())

 

Инициализируем списки.

 

g = [[0] * (n + 1) for _ in range(n + 1)]

used = [0] * (n + 1)

 

Строим матрицу смежности графа.

 

for i in range(m):

  a, b = map(int, input().split())

  g[a][b] = g[b][a] = 1

 

Запускаем поиск в глубину из вершины 1.

 

cnt = 0

dfs(1)

 

Если в результате поиска в глубину были посещены все n вершин, то граф связный.

 

if cnt == n:

  print("YES")

else:

  print("NO")

 

Python реализация алгоритма – система непересекающихся множеств

Функция Repr возвращает номер вершины – представителя множества, содержащего вершину n. Двигаемся по указателю на следующий элемент, пока не встретим представителя множества (его указатель указывает на него самого).

 

def Repr(n):

  while n != mas[n]:

    n = mas[n]

  return n

 

Функция Union объединяет два множества, содержащие вершины x и y. Ищем представителей множеств, содержащих x и y. Пусть этими представителями будут x1 и y1. Если x1 = y1, то x и y уже находятся в одном множестве, и в таком случае ничего делать не надо. В противном случае указатель представителя x1 перенаправляем на y1.

 

def Union(x, y):

  x1 = Repr(x)

  y1 = Repr(y)

  if x1 == y1: return

  mas[x1] = y1

 

Основная часть программы. Читаем входные данные.

 

n, m = map(int, input().split())

 

Изначально каждая вершина указывает сама на себя (mas[i] = i).

 

mas = [0] * (n + 1)

for i in range(1, n + 1):

  mas[i] = i

 

Читаем ребра графа. Для каждого ребра (a, b) совершаем объединение множеств, содержащих вершины a и b.

 

for _ in range(m):

  a, b = map(int, input().split())

  Union(a, b)

 

Подсчитываем количество компонент связности в переменной count. Оно равно количеству вершин – представителей множеств (которые указывают сами на себя).

 

count = 0

for i in range(1, n + 1):

  if mas[i] == i:

    count += 1

 

В зависимости от значения переменной count выводим ответ.

 

if count == 1:

  print("YES")

else:

  print("NO")