e-olimp 1667. Конденсация графа

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

Входные данные

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex] до [latex]N[/latex] — номера начала и конца ребра.

Выходные данные

В первой строке выведите число [latex]K[/latex] — количество компонент сильной связности в заданном графе. В следующей строке выведите [latex]N[/latex] чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

Иллюстрация ко второму тесту:

Код программы:

#include <iostream>
#include <vector>
using namespace std;

vector <int> G[100010];
vector <int> Gt[100010]; // транспонированній граф
vector<bool> used;
vector<int> order, component;
int res[100010];
int n, m, num=1;

void dfs_1 (int u) {
 used[u]=1;
 for (int i=0; i<G[u].size(); i++) {
     if (used[G[u][i]]==0) {
         dfs_1(G[u][i]);
     }
 }
 order.push_back(u);
}

void dfs_2 (int u) {
  used[u]=1;
  component.push_back(u);
  for (int i=0; i<Gt[u].size(); i++) {
      if (used[Gt[u][i]]==0) {
          dfs_2 (Gt[u][i]);
      }
  }
}

int main() {
 ios::sync_with_stdio(false);
 cin >> n >> m;
 
 while (m--) {
     int a, b;
     cin >> a >> b;
     a--;
     b--;
     G[a].push_back(b);
     Gt[b].push_back(a);
 }
 
 used.assign (n, false);

 for (int i=0; i<n; i++) {
         if (used[i]==0) dfs_1(i);
 }
 
 used.assign (n, false);
 
 for (int i=0; i<n; i++) {
      int v=order[n-1-i];
      if (used[v]==0) {
          dfs_2 (v);
          for(auto I=component.begin(); I!=component.end(); I++)
              res[*I]=num;
          num++;
          component.clear();
      }
  }
  
  cout << num-1 << endl;
  for (int i=0; i<n-1; i++) cout << res[i] << " ";
  cout << res[n-1] << endl;
  return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

vector <int> Gt[100010]; // транспонированній граф

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

for (int i=0; i<G[u].size(); i++) {

if (used[G[u][i]]==0) {

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

for (int i=0; i<Gt[u].size(); i++) {

if (used[Gt[u][i]]==0) {

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

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

if (used[i]==0) dfs_1(i);

}

used.assign (n, false);

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

int v=order[n-1-i];

if (used[v]==0) {

dfs_2 (v);

for(auto I=component.begin(); I!=component.end(); I++)

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

for (int i=0; i<n-1; i++) cout << res[i] << " ";

cout << res[n-1] << endl;

return 0;

}

Алгоритм решения

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

Научившись это делать, мы сможем постепенно выделить все компоненты сильной связности: удалив из графа вершины первой выделенной компоненты, мы снова найдём среди оставшихся вершину с наибольшим временем выхода, снова запустим из неё этот обход, и так далее.

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

Related Images:

Похожее

One thought on “e-olimp 1667. Конденсация графа”

Мазурок Игорь Евгеньевич says: 13/04/2015 at 16:25

Хорошее решение, толковое описание. Молодец. Зачтено.

Формула не отображалась из-за использования кириллицы вместо латинской М.

Войдите, чтобы ответить