вторник, 28 августа 2012 г.

Нахождение количества компонент связности

Рассмотрим базовую задачу.
Условие:
Дан неориентированный граф 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




Компонента связности неориентированного графа является подграф, в котором для любой пары вершин v и u существует путь. Между двумя различными компонентами связности не существует пути.

Задача стара, как мир. Но тем не менее сегодня покажу несколько подходов по ее решению.

1. Поиск в глубину(DFS)
Самое классическое решение. Даже комментировать особо нечего.

  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 принципиально разных подхода. На маленьких ограничениях можно выбрать тот из них, что больше по душе.