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

2 комментария:

  1. Подскажите, пожалуйста, с алгоритмом для поиска всё того же кол-ва компонент, но с условием, что граф ориентированный

    ОтветитьУдалить
  2. Did you hear there's a 12 word sentence you can tell your partner... that will induce deep emotions of love and instinctual attractiveness for you buried inside his heart?

    Because deep inside these 12 words is a "secret signal" that triggers a man's instinct to love, look after and protect you with his entire heart...

    ===> 12 Words Who Fuel A Man's Love Response

    This instinct is so hardwired into a man's genetics that it will drive him to try better than ever before to take care of you.

    In fact, triggering this influential instinct is so important to getting the best ever relationship with your man that once you send your man a "Secret Signal"...

    ...You will soon notice him expose his soul and mind for you in a way he never experienced before and he'll distinguish you as the one and only woman in the galaxy who has ever truly attracted him.

    ОтветитьУдалить