Как найти число компонент связности графа

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Рассмотрим базовую задачу.
Условие:
Дан неориентированный граф G, имеющий N вершин и M ребер. Чтобы все рассмотренные подходы имели практических смысл, ограничим N<=1000.
Необходимо найти количество компонент связности данного графа. Формат входных данных: В первой строке входного файла находятся N и M, разделенные пробелом. Далее идет M строк, содержащих пару вершин, между которыми находится ребро. Вершины нумеруются с 1.
Формат выходных данный: В единственной строке выдать количество компонент связности графа.

Пример:
input.txt
15 11
1 2
2 3
2 11
10 11
11 12
11 15
4 12
12 13
8 14
7 14
5 6
output.txt
4

1. const int SIZE = 1e3 + 10;
2. vector<int> adj[SIZE];
3. bool usd[SIZE];
4. ...
5. void dfs(int cur) {
6.   usd[cur] = true;
7.   for (int i=0;i<adj[cur].size();++i) {
8.     int nxt = adj[cur][i];
9.     if (!usd[nxt])
10.       dfs(nxt);
11.   }
12. }
13. int connected_components_amount_dfs() {
14.   int cnt = 0;
15.   for (int i=1; i<=n; ++i) {
16.     if (!usd[i]) {
17.       dfs(i);
18.       ++cnt;
19.     }
20.   }
21.   return cnt;
22. }

* This source code was highlighted with Source Code Highlighter.

Граф храним в виде списка смежности(строка 2). Общая сложность решения $latex O(N + M)$.
Решение

2. DSU подобная структура(ленивый подход)
Будем делать конденсацию компоненты в одну вершину. Идея следующая: будем последовательно обрабатывать ребра. Каждая компонента связности будет представлена одной своей вершиной(титульная). При этом неважно какой. По ходу обработки ребер титульная вершина компонент может меняться.
В итоге для нахождения количества компонент связности нужно найти количество титульных вершин.

1. const int SIZE = 1e3 + 10;
2. int p[SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_dsu() {
6.  
7.   scanf("%d %d", &n, &m);
8.  
9.   for (int i=1;i<=n;++i) {
10.     p[i] = i;
11.   }
12.  
13.   for (int i=0;i<m;++i) {
14.     scanf("%d %d", &f, &s);
15.     int par = p[f];
16.     for (int j=1;j<=n;++j) {
17.       if (p[j] == par)
18.         p[j] = p[s];
19.     }
20.   }
21.   for (int i=1;i<=n;++i)
22.     usd[p[i]] = true;
23.   int cnt = 0;
24.   for (int i=1;i<=n;++i) {
25.     if (usd[i]) ++cnt;
26.   }
27.   return cnt;
28. }

* This source code was highlighted with Source Code Highlighter.

Заметим, что сам граф непосредственно вообще никак не хранится. Общая сложность $latex O(M*N)$ 
Решение

3. Система непересекающихся множеств (DSU)
Реализацию, представленную выше можно существенно усовершенствовать. При добавлении нового ребра будем “мерджить меньшее подмножество к большему” + сжимать пути. У emaxx’а рассматривается доказательство того, что ассимптотика обработки одного ребра равна $latex O(alpha (N))$, где $latex alpha (N)$ – обратная функция Аккермана.

1. const int SIZE = 1e3 + 10;
2.  
3. int p[SIZE];
4. int size[SIZE];
5.  
6. int par(int x) {
7.   return p[x] == x ? x : p[x] = par(p[x]);
8. }
9. int connected_components_amount_dsu() {
10.  
11.   scanf("%d %d", &n, &m);
12.  
13.   for (int i=1;i<=n;++i) {
14.     p[i] = i;
15.     size[i] = 1;
16.   }
17.  
18.   for (int i=0;i<m;++i) {
19.     scanf("%d %d", &f, &s);
20.     f = par(f); s = par(s);
21.     if (f != s) {
22.       if (size[f] > size[s])
23.         swap(f,s);
24.       p[f] = s;
25.       size[s] += size[f];
26.     }
27.   }
28.   bool usd[SIZE];
29.   memset(usd, 0, sizeof(usd));
30.   for (int i=1;i<=n;++i)
31.     usd[par(i)] = true;
32.   int cnt = 0;
33.   for (int i=1;i<=n;++i) {
34.     if (usd[i]) ++cnt;
35.   }
36.  
37.   return cnt;
38. }

* This source code was highlighted with Source Code Highlighter.

Как и прежде сам граф не хранится в виде матрицы смежности. Общая сложность $latex O(M * alpha (N))$

4. Алгоритм Флойда.
Этот подход для самых ленивых, правда он требует хранить граф явно в виде матрицы смежности.
Запускаем алгоритм Флойда и строим матрицу достижимости для каждой пары вершин. В результате если первоначально adj[u][v] указывало на наличие ребра между u и v, то после работы алгоритма adj[u][v] будет указывать на наличие пути между u и v. После чего можно написать DFS двумя вложенными циклами.

1. const int SIZE = 1e3 + 10;
2. int adj[SIZE][SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_floyd() {
6.  
7.   for (int k=1;k<=n;++k){
8.     for (int i=1;i<=n;++i){
9.       for (int j=1;j<=n;++j){
10.         if (adj[i][k] + adj[k][j] == 2)    
11.           adj[i][j] = 1;
12.       }
13.     }
14.   }
15.  
16.   int cnt = 0;
17.   for (int i=1;i<=n;++i) {
18.     if (!usd[i]) {
19.       ++cnt;
20.       usd[i] = true;
21.       for (int j=1;j<=n;++j) {
22.         if (adj[i][j] && !usd[j])
23.           usd[j] = true;
24.       }
25.     }
26.   }
27.   return cnt; 
28. }

* This source code was highlighted with Source Code Highlighter.

Алгоритм ужасно долгий, но зато пишется довольно просто. Общая сложность $latex O({ N }^{ 3 }) $
Решение

Собственно пока и все. Мы рассмотрели 3 принципиально разных подхода. На маленьких ограничениях можно выбрать тот из них, что больше по душе.