Как найти все компоненты сильной связности

Поиск компонент сильной связности: алгоритм Косарайю

Время на прочтение
2 мин

Количество просмотров 33K

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

К делу:

Заметим: отношение сильной связности — это отношение эквивалентности.

$1)Рефлексивность: forall v v to v$

$2)Симметричность: forall v forall u v to u => u to v$

$3) Транзитивность: forall v forall u forall t v to u wedge u to t => v to t $

Компонентой сильной связности называется класс эквивалентности множества вершин ориентированного графа относительно отношения сильной связности. Другими словами компонента сильной связности = сильно связный подграф. Так как сильная связность — это отношение эквивалентности, то граф разбивается на сильно связные компоненты. Наша задача найти все такие классы эквивалентности.

Алгоритм Косарайю

  • Инвертированием ориентированного графа назовем процедуру, в ходе которой поменяем направление каждого ребра на противоположное.

Метод Косарайю прост для реализации и понимания. Так как компоненты сильной связности есть циклы, то они совпадают и у исходного графа и у его инвертирования.

Пусть дан ориентированный граф G = (V, E). Через G’ = (V, E’) обозначим интертирование G.

Будем обходить граф G в глубину, пока не посетим все вершины. Заведем массив out = [0…|V|-1] — время выхода из вершины. Под временем понимаются логические часы: изначально время равно 0, при переходе в вершину или выходе из неё время увеличивается на 1.


Когда обход закончится, заведем массив vertices, куда добавим все вершины в порядке увеличения времени выхода. Теперь запустим обход в глубинку на инвертированном графе G’. Каждый раз для обхода будем выбирать ещё не посещенную вершину с максимальным индексом в массиве vertices. Все вершины, посещенные в ходе одной итерации dfs, образуют компоненту сильной связности.

Время работы

Заметим: если граф представлен графом смежности, то нам не требуетcя хранить в памяти инвертированный граф. Иначе нам потребуется O(V+E) доп. памяти. Но, в любом случае, нам требуется O(V) памяти для массивов out и vertices.

Алгоритм состоит из двух обходов DFS. Каждый работает пропорционально V+E для разреженных графов и V^2 для насыщенных. Кроме того, нам требуется O(VlogV) для сортировки вершин при построении массива vertices.

Дополнительно

Корректность алгоритма и псевдокод можно посмотреть тут: www.jeffreykarres.com/blog/kosaraju

В начале статьи я упоминал приложения.

  • На SO писали про использование этого алгоритма для формальной верификации:
    stackoverflow.com/questions/11212676/what-are-strongly-connected-components-used-for
  • А про экологию можно почитать в статье:
    www.nceas.ucsb.edu/~allesina/PDF/Allesina2005.pdf
Источник

Содержание

  • 1 Алгоритм
  • 2 Доказательство корректности алгоритма
  • 3 Время работы алгоритма
  • 4 Псевдокод
  • 5 Источники информации

Алгоритм

Вершины 2, 4, 5 сильносвязаны.
Синим цветом обозначен обод DFS по инвертированным ребрам

Компоненты сильной связности в графе можно найти с помощью поиска в глубину в 3 этапа:

  1. Построить граф с обратными (инвертированными) рёбрами
  2. Выполнить в поиск в глубину и найти — время окончания обработки вершины
  3. Выполнить поиск в глубину в , перебирая вершины во внешнем цикле в порядке убывания

Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа .
Так как компоненты сильной связности и графа совпадают, то первый поиск в глубину для нахождения можно выполнить на графе , а второй — на .

Доказательство корректности алгоритма

Теорема:

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

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

  1. Вершины и лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня этого дерева.
  2. Вершина была рассмотрена вторым обходом в глубину раньше, чем и , значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин и . Из этого мы получаем 2 случая:
    1. Обе эти вершины были достижимы из в инвертированном графе. А это означает взаимную достижимость вершин и и взаимную достижимость вершин и . А складывая пути мы получаем взаимную достижимость вершин и .
    2. Хотя бы одна не достижима из в инвертированном графе, например . Значит и была не достижима из в инвертированном графе, так как время выхода — больше . Значит между этими вершинами нет пути, но последнего быть не может, потому что была достижима из по пункту 1).

Значит, из случая 2.1 и не существования случая 2.2 получаем, что вершины и взаимно достижимы в обоих графах.

Время работы алгоритма

  1. Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.
  2. Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за
  3. Поиск в глубину в исходном графе выполняется за .

В итоге получаем, что время работы алгоритма .

Псевдокод

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

   function dfs1(v):                                          
       color[v] = 1
       for (v, u) in E
           if not visited[u]
               dfs1(G[v][u])
       Добавляем вершину v в конец списка ord
   
   function dfs2(v):                                          
       component[v] = col
       for (v, u) in E
           if (вершина u еще не находится ни в какой компоненте)                       
               dfs2(H[v][u])
   
   function main():
       считываем исходные данные, формируем массивы G и H
       for u in V                           
           if not visited[u]
               dfs1(u)
       col = 1
       for (по всем вершинам u списка ord[] в обратном порядке)                                                        
           if (вершина u не находится ни в какой компоненте)
               dfs2(u)
               col++

Источники информации

  • Р.Седжвик. «Фундаментальные алгоритмы на С++. Алгоритмы на графах» — СПб, ДиаСофтЮП, 2002
  • MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа
  • Визуализация поиска компонент сильной связности
Источник

Ранее мы научились топологически сортировать ациклические графы. Но в циклических графах тоже иногда требуется найти какую-то структуру, для чего нам нужно ввести понятие сильной связности.

Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.

Понятно, что такое отношение транзитивно: если $a$ и $b$ сильно связны, и $b$ и $c$ сильно связны, то $a$ и $c$ тоже сильно связны. Поэтому все вершины распадаются на компоненты сильной связности — такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильной связности нет.

Граф с тремя компонентами сильной связности

Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.

Часто рассматривают граф, составленный из самих компонент сильной связности, а не индивидуальных вершин. Очевидно, такой граф уже будет ациклическим, и с ним проще работать. Задачу о сжатии каждой компоненты сильной связности в одну вершину называют конденсацией графа, и её решение мы сейчас опишем.

#Конденсация графа

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

Лемма. Запустим dfs. Пусть $A$ и $B$ — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро $A to B$. Тогда:

$$
maxlimits_{a in A}(tout_a) > maxlimits_{bin B}(tout_b)
$$

Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.

Пусть первой была достигнута компонента $A$, то есть в какой-то момент времени dfs заходит в некоторую вершину $v$ компоненты $A$, и при этом все остальные вершины компонент $A$ и $B$ ещё не посещены. Но так как по условию в графе конденсаций есть ребро $A to B$, то из вершины $v$ будет достижима не только вся компонента $A$, но и вся компонента $B$. Это означает, что при запуске из вершины $v$ обход в глубину пройдёт по всем вершинам компонент $A$ и $B$, а, значит, они станут потомками по отношению к $v$ в дереве обхода, и для любой вершины $u in A cup B, u ne v$ будет выполнено $tout_v] > tout_u$, что и утверждалось.

Второй случай проще: из $B$ по условию нельзя дойти до $A$, а значит, если первой была достигнута $B$, то dfs выйдет из всех её вершин ещё до того, как войти в $A$.

Из этого факта следует первая часть решения. Отсортируем вершины по убыванию времени выхода (как бы сделаем топологическую сортировку, но на циклическом графе). Рассмотрим компоненту сильной связности первой вершины в сортировке. В эту компоненту точно не входят никакие рёбра из других компонент — иначе нарушилось бы условие леммы, ведь у первой вершины $tout$ максимальный. Поэтому, если развернуть все рёбра в графе, то из этой вершины будет достижима своя компонента сильной связности $C^prime$, и больше ничего — если в исходном графе не было рёбер из других компонент, то в транспонированном не будет ребер в другие компоненты.

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

vector<int> g[maxn], t[maxn];
vector<int> order;
bool used[maxn];
int component[maxn];
int cnt_components = 0;

// топологическая сортировка
void dfs1(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) 
            dfs1(u);
    order.push_back(v);
}

// маркировка компонент сильной связности
void dfs2(int v) {
    component[v] = cnt_components;
    for (int u : t[v])
        if (component[u] == 0)
            dfs2(u);
}


// в содержательной части main:

// транспонируем граф
for (int v = 0; v < n; v++)
    for (int u : g[v])
        t[u].push_back(v);

// запускаем топологическую сортировку
for (int i = 0; i < n; i++)
    if (!used[i])
        dfs1(i);

// выделяем компоненты
reverse(order.begin(), order.end());
for (int v : order)
    if (component[v] == 0)
        dfs2(v), cnt_components++;

TL;DR:

  1. Сортируем вершины в порядке убывания времени выхода.
  2. Проходимся по массиву вершин в этом порядке, и для ещё не помеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компоненты связности.

После этого номера компонент связности будут топологически отсортированы.

Источник

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

Ориентированный
граф называется сильно
связным,
если для любых двух его вершин


и


существует
хотя бы один путь, соединяющий


с

.
Ориентированный граф называется
односторонне
связным,
если для любых двух его вершин, по крайней
мере, одна достижима из другой.

Компонентой
связности неориентированного графа
называется его связный подграф, не
являющийся собственным подграфом
никакого другого связного подграфа
данного графа (максимально связный
подграф).

Компонентой
сильной связности ориентированного
графа
называется его сильно связный подграф,
не являющийся собственным подграфом
никакого другого сильно связного
подграфа данного графа (максимально
сильно связный подграф).

Компонентой
односторонней связности ориентированного
графа называется
его односторонне связный подграф, не
являющийся собственным подграфом
никакого другого односторонне связного
подграфа данного графа (максимально
односторонне связный подграф).

Пусть

неориентированный граф с множеством
вершин

.
Квадратная матрица


порядка

,
у которой


называется
матрицей
связности графа

.

Для ориентированного
графа квадратная матрица

порядка

,
у которой

называется
матрицей
односторонней связности (достижимости).

Квадратная матрица

порядка

,
у которой

называется матрицей
сильной связности.

Пример. У
неориентированного графа, изображенного
на рис. 22 две компоненты связности.
Первая компонента связности включает
вершины

,
а вторая
состоит из одной вершины

.

Рис. 22. Компоненты
связанности неориентированного графа

Матрица связности
этого графа имеет вид:

.

Мы видим, что 1-ая,
2-ая, 4-ая и 5-ая строки матрицы

одинаковы.

Пример. У
ориентированного графа, изображенного
на рис. 23 две компоненты сильной связности.
Первая компонента связности включает
вершины

,
а вторая
состоит из одной вершины

.
Действительно, для любой пары вершин
из множества


существует
хотя бы один путь, соединяющий эти
вершины. Например, путь

соединяет все эти вершины. Из вершины

нет пути ни в одну вершину графа.

Рис. 23. Компоненты
сильной связанности ориентированного
графа

Матрица сильной
связности этого графа имеет вид:


.

Заметим, что 1-ая,
2-ая, 3-ая и 5-ая строки матрицы

одинаковы.

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

ориентированного графа, затем находим
матрицу сильной связности

ориентированного графа (она должна быть
симметрической).

Алгоритм выделения
компонента сильной связности:

1. Присваиваем

(

− количество компонент связности),


.

2. Включаем в
множество вершин


компоненты
сильной связности

вершины, соответствующие единицам
первой строки матрицы

.
В качестве матрицы смежности

возьмем подматрицу матрицы

,
состоящую из элементов матрицы

,
находящихся на пересечении строк и
столбцов, соответствующих вершинам из

.

3. Вычеркиваем из

строки и столбцы, соответствующие
вершинам из

.
Если не остается ни одной строки (и
столбца), то


количество компонент сильной связности.
В противном случае обозначим оставшуюся
после вычеркивания срок и столбцов
матрицу как

,
присваиваем

и переходим к п. 2.

Пример. Выделим
компоненты связности ориентированного
графа, изображенного на рис. 25. Количество
вершин

.

Рис. 25.

Значит, для данного
ориентированного графа матрица смежности
будет иметь размерность

и будет выглядеть следующим образом


.

Найдем матрицу
достижимости и матрицу сильной связности
для данного ориентированного графа:


,


.

Присваиваем

,

и составляем множество вершин первой
компоненты сильной связности

:
это те вершины, которым соответствуют
единицы в первой строке матрицы

.
Таким образом, первая компонента сильной
связности состоит из одной вершины

.

Вычеркиваем из
матрицы

строку и столбец, соответствующие
вершине

,
чтобы получить матрицу

.

Присваиваем

.
Множество вершин второй компоненты
связности составят те вершины, которым
соответствуют единицы в первой строке
матрицы

,
то есть

.
Составляем матрицу смежности для
компоненты сильной связности

исходного графа


− в ее
качестве возьмем подматрицу матрицы

,
состоящую из элементов матрицы

,
находящихся на пересечении строк и
столбцов, соответствующих вершинам из

:


.

Вычеркиваем из
матрицы

строки и столбцы, соответствующие
вершинам из

,чтобы
получить матрицу

,
которая состоит из одного элемента

,
присваиваем

.
Таким образом, третья компонента сильной
связности исходного графа, как и первая,
состоит из одной вершины

.

Таким образом,
выделены 3 компоненты сильной связности
ориентированного графа

:

:


:


:

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

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
Источник

Взаимная достижимость, компоненты сильной связности и базы графа

По аналогии с графом достижимости определим граф сильной достижимости.

Определение 9.10. Пусть G=(V,E) — ориентированный граф. Граф сильной достижимости G**=(V,E**) для G имеет то же множество вершин V
и следующее множество ребер E** ={ (u, v) | в графе G вершины v и u взаимно достижимы}.

По матрице графа достижимости A_{G^*} легко построить матрицу A_{G_*^*} графа
сильной достижимости.
Действительно из определений достижимости и сильной достижимости непосредственно
следует, то для всех пар (i,j), 1<= i,j <= n, значение элемента A_{G_*^*}(i,j) равно 1 тогда и только тогда,
когда оба элемента AG*(i, j) и AG*(j, i) равны 1, т.е.

A_{G_*^*}(i,j) = A_{G^*}(i, j) wedge A_{G^*}( j, i)

По матрице A_{G_*^*} можно выделить компоненты сильной связности графа G следующим образом.

  1. Поместим в компоненту K1 вершину v1 и все такие вершины vj, что A_{G_*^*}(1,j) = 1.
  2. Пусть уже построены компоненты K1, …, Ki и vk — это вершина с минимальным номером, еще не попавшая в компоненты. Тогда поместим в компоненту K_{i+1} вершину vk и все такие вершины vj,
  3. что A_{G_*^*}(k,j) = 1.

Повторяем шаг (2) до тех пор, пока все вершины не будут распределены по компонентам.

В нашем примере для графа G на рис.2 по матрице A_{G^*} получаем
следующую матрицу графа сильной достижимости

A_{G_*^*}= left( begin{array}{cccccc} 1 & 1 & 1 & 0& 0& 0\ 1 & 1 & 1 & 0& 0& 0\ 1 &1 & 1 & 0& 0& 0\ 0 & 0 & 0 & 1& 0& 0\ 0 & 0 & 0 & 0& 1& 0\ 0 & 0 & 0 & 0& 0& 1 end{array}right).

Используя описанную выше процедуру, находим, что вершины графа G разбиваются на 4 компоненты сильной связности: K1= {v1, v2, v3}, K2 ={ v4}, K3 ={ v5}, K4 ={ v6}.

На множестве компонент сильной связности также определим отношение достижимости.

Определение 9.11. Пусть K и K’ — компоненты сильной связности графа G.
Компонента K достижима из компоненты K^prime, если K= K’
или существуют такие две вершины u in K
и v in K', что u достижима из v. K строго достижима из K^prime, если Kne K' и K достижима из K’.

Компонента K называется минимальной, если она не является строго
достижимой ни из какой компоненты.

Так как все вершины в одной компоненте взаимно достижимы, то нетрудно понять,
что отношения достижимости и строгой достижимости на компонентах не зависят
от выбора вершин u in K и v in K'.

Из определения легко выводится следующая характеристика строгой достижимости.

Лемма 9.3.
Отношение строгой достижимости является отношением частичного порядка, т.е. оно
антирефлексивно, антисимметрично и транзитивно.

Это отношение можно представлять в виде ориентированного графа, вершинам и которого
являются компоненты, а ребро (K’, K) означает, что K строго достижима из K’.
На рис. 9.4 показан этот граф компонент для рассматриваемого выше графа G.

Граф отношения достижимости на компонентах G

Рис.
9.4.
Граф отношения достижимости на компонентах G

В данном случае имеется одна минимальная компонента K2.

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

Определение 9.12. Пусть G=(V,E) — ориентированный граф.
Подмножество вершин W subseteq V называется порождающим,
если из вершин W
можно достичь любую вершину графа.
Подмножество вершин W subseteq V называется базой графа,
если оно является порождающим,
но никакое его собственное подмножество порождающим не является.

Следующая теорема позволяет эффективно находить все базы графа.

Теорема 9.1.
Пусть G=(V,E) — ориентированный граф. Подмножество вершин W subseteq V
является базой G тогда и только тогда, когда содержит по одной вершине из каждой
минимальной компоненты сильной связности G и не содержит никаких других вершин.

Доказательство Заметим вначале, что каждая вершина графа достижима из вершины,
принадлежащей некоторой минимальной компоненте. Поэтому множество вершин W,
содержащих по одной вершине из каждой минимальной компоненты, является порождающим
а при удалении из него любой вершины перестает быть таковым, так как вершины из
соответствующей минимальной компоненты становятся недостижимы. Поэтому W является базой.

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

Из этой теоремы вытекает следующая процедура построения одной или перечисления всех баз графа G.

  1. Найти все компоненты сильной связности G.
  2. Определить порядок на них и выделить минимальные относительно этого порядка компоненты.
  3. Породить одну или все базы графа, выбирая по одной вершине из каждой минимальной компоненты.

Пример 9.5.
Определим все базы ориентированного графа G, показанного на рис.9.5.

Граф G

Рис.
9.5.
Граф G

На первом этапе находим компоненты сильной связности G:

K_1 ={ a, n, l }, K_2 = { b }, K_3 ={ c}, K_4 ={ d,e, f, g}, \ K_5={ h, m}, K_6 ={ k}, K_7= { r}

На втором этапе строим граф строгой достижимости на этих компонентах.

Граф отношения достижимости на компонентах G

Рис.
9.6.
Граф отношения достижимости на компонентах G

Определяем минимальные компоненты: K2 = { b }, K4 ={ d,e, f, g} и K7= { r}.

Наконец перечисляем все четыре базы G: B1= { b, d, r}, B2= { b, e, r}, B3= { b, f, r} и B1= { b, g, r}.

Задачи

Задача 9.1. Докажите, что сумма степеней всех вершин произвольного ориентированного графа четна.

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

Задача 9.2. Перечислите все неизоморфные неориентированные графы, у которых не
более четырех вершин.

Задача 9.3.
Докажите, что неориентированный связный граф остается связным после
удаления некоторого ребра leftrightarrow это ребро принадлежит некоторому циклу.

Задача 9.4.
Докажите, что неориентированный связный граф с n вершинам и

  • содержит не менее n-1 ребер,
  • если содержит больше n-1 ребер, то имеет, по крайней мере, хотя бы один цикл.

Задача 9.5.
Докажите, что в любой группе из 6 человек есть трое попарно знакомых или
трое попарно незнакомых.

Задача 9.6.
Докажите, что неориентированный граф G=(V,E) связен leftrightarrow
для каждого разбиения V= V_{1}cup V_{2} с непустыми V1 и V2 существует ребро, соединяющее V1 с V2.

Задача 9.7.
Докажите, что, если в неориентированном графе имеется ровно две вершины нечетной
степени, то они связаны путем.

Задача 9.8.
Пусть G=(V,E) неориентированный граф с |E| < |V|-1. Докажите, что тогда G несвязный граф.

Задача 9.9. Докажите, что в связном неориентированном графе
любые два простых пути максимальной длины имеют общую вершину.

Задача 9.10.
Пусть неориентированный граф без петель G=(V,E) имеет k компонент связности. Доказать, что тогда

|E| leq (|V| -k)(|V|-k +1)/2

Задача 9.11. Определите, что представляет из себя граф достижимости для

  • графа с n вершинам и и пустым множеством ребер;

  • графа с n вершинам и: V= {v1,… , vn}, ребра которого образуют цикл:

    E ={(v_1,v_2), (v_2,v_3), ldots , (v_{n-1},v_n), (v_n,v_1) }.

Задача 9.12. Вычислите матрицу графа достижимости A_{G^*} для графа

G=({a,b,c,d,e,f, g}, { (a,b), (b,a), (a,c), (b,d), (e,d), \(d, f), (f,c), (c,f), (g,e)}

и постройте соответствующий ей граф достижимости. Найдите все базы графа G.

Задача 9.13.
Построить для заданного на рис. 9.7 ориентированного графа G1=(V,E)
его матрицу смежности AG1, матрицу инцидентности BG1
и списки смежности. Вычислить матрицу достижимости AG1*
и построить соответствующий граф достижимости G1*.

Рис.
9.7.

Источник

Понравилась статья? Поделить с друзьями:
  • Составьте четыре предложения с обращениями выраженными как одушевленными
  • Как найти дома на обслуживание
  • Как исправить неаттестацию в колледже
  • Как найти собаку в подмосковье
  • Как найти свою анкету на профи ру