776. Дороги

В Украине, как известно, существует множество проблем, одна из которых – состояние дорог. Новый президент Украины решил сосредоточиться на строительстве дорожной инфраструктуры. Его цель – проложить дополнительное количество дорог между городами так, чтобы из любого города можно было добраться до любого другого (возможно, через другие города, не обязательно напрямую). Естественно, количество новых дорог должно быть минимальным.

Предположим, что все дороги в Украине двухсторонние (как уже существующие, так и те, которые предстоит построить), то есть движение по ним возможно в обоих направлениях. При этом между двумя городами может быть несколько дорог, а также могут существовать дороги, связывающие город с самим собой.

Вход. Первая строка содержит два натуральных числа n и m (1 ≤ n, m ≤ 10000) – количество городов и количество уже существующих дорог. Следующие m строк содержат по два целых числа a_i и b_i (1 ≤ a_i, b_i ≤ n) – номера городов, которые соединены уже существующей дорогой.

Выход. Выведите минимальное количество дорог, которое необходимо построить, чтобы из любого города можно было добраться до любого другого.

Пример входа	Пример выхода
7 5 1 3 2 3 3 2 2 4 6 7	2

РЕШЕНИЕ

графы – поиск в глубину

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

Поскольку граф содержит 10000 вершин, то воспользуемся списком смежности для его хранения. По входному списку ребер построим список смежности. При помощи поиска в глубину найдем количество компонент связности. Число новых дорог, которые следует построить, равно количеству компонент связности минус 1.

Пример

Приведенный в примере граф имеет вид:

Граф содержит 3 компоненты связности. Для их соединения достаточно добавить 2 ребра.

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

Объявим список смежности g и массив used, в котором будем отмечать пройденные вершины.

vector<vector<int> > g;

vector<int> used;

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

void dfs(int v)

{

used[v] = 1;

for (int i = 0; i < g[v].size(); i++)

{

int to = g[v][i];

if (!used[to]) dfs(to);

}

}

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

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

g.resize(n + 1);

Читаем m ребер, строим список смежности графа.

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

{

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

g[a].push_back(b);

g[b].push_back(a);

}

Запускаем поиск в глубину на несвязном графе. В переменной cnt подсчитываем количество компонент связности.

used.resize(n + 1);

cnt = 0;

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

if (used[i] == 0)

{

dfs(i);

cnt++;

}

Выводим количество дорог, которое следует построить.

printf("%d\n", cnt - 1);

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

#include <stdio.h>

#define MAX 10001

int mas[MAX];

int Repr(int n)

{

while (n != mas[n]) n = mas[n];

return n;

}

void Union(int x, int y)

{

int x1 = Repr(x), y1 = Repr(y);

if (x1 == y1) return;

mas[x1] = y1;

}

int a, b, i, j, n, m, count;

int main(void)

{

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

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

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

{

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

Union(a, b);

}

count = 0;

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

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

printf("%d\n", count - 1);

return 0;

}

Java реализация

import java.util.*;

public class Main

{

static ArrayList<Integer>[] g;

static boolean used[];

static int n, m;

static void dfs(int v)

{

used[v] = true;

for(int i = 0; i < g[v].size(); i++)

{

int to = g[v].get(i);

if (used[to] == false) dfs(to);

}

}

@SuppressWarnings("unchecked")

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

n = con.nextInt();

m = con.nextInt();

used = new boolean[n+1];

g = new ArrayList[n+1];

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

g[i] = new ArrayList<Integer>();

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

{

int a = con.nextInt();

int b = con.nextInt();

g[a].add(b);

g[b].add(a);

}

int cnt = 0;

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

if (used[i] == false)

{

dfs(i);

cnt++;

}

System.out.println(cnt - 1);

con.close();

}

}

Python реализация

Увеличим стек для рекурсии.

import sys
sys.setrecursionlimit(1000000)
 

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

 
def dfs(v):
 used[v] = 1
 for to in g[v]:
 if not used[to]:
 dfs(to)
 

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

 
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
used = [0] * (n + 1)
 

Читаем m ребер, строим список смежности графа.

 
for _ in range(m):
 a, b = map(int, input().split())
 g[a].append(b)
 g[b].append(a)
 

Запускаем поиск в глубину на несвязном графе. В переменной cnt подсчитываем количество компонент связности.

 
cnt = 0
for i in range(1, n + 1):
 if not used[i]:
 dfs(i)
 cnt += 1
 

Выводим количество дорог, которое следует построить.

 
print(cnt - 1)