6818. Capital City

There are N cities in Flatland connected with M unidirectional roads. The cities are numbered from 1 to n. The Flat Circle of Flatland (FCF) wants to set up a new capital city for his kingdom. For security reasons, the capital must be reachable from all other cities of Flatland. FCF needs the list of all candidate cities. You are the chief programmer at FACM (Flat Association for Computing Machinery) responsible for providing the list to FCF as soon as possible.

Input. The first line contains two integers n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 200000). Each of the following m lines contains two integers a, b (1 ≤ a, b ≤ n) denoting a road from a to b.

Output. The output file contains an integer denoting the number of candidate cities followed by the list of candidate cities in increasing order.

Sample Input	Sample output
4 4 1 2 3 2 4 3 2 1	2 1 2

РЕШЕНИЕ

сильная связность графа

Анализ алгоритма

В задаче следует вывести все такие номера городов, в которые можно попасть со всех остальных. Выделим в графе компоненты сильной связности. Ищем ССК, из которых нет исходящих ребер в другие ССК. Пусть такими будут компоненты А и В. Тогда где бы ни находилась столица (в А, в В или вне их), попасть в нее одновременно из вершин компоненты А и из вершин компоненты В невозможно. То есть если количество ССК, из которых нет исходящих ребер, больше 1, то ответ 0 (искомых столиц не существует).

Если такая компонента единственная, то выводим ее размер и номера всех ее вершин..

Пример

Граф из теста имеет вид:

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

Реализация алгоритма

#include <cstdio>

#include <vector>

using namespace std;

vector<vector<int> > g, gr;

vector<int> used, top, color;

int i, j, a, b, n, m, v, to, c, res, col;

void dfs1(int v)

{

int i, to;

used[v] = 1;

for(i = 0; i < g[v].size(); i++)

{

to = g[v][i];

if (!used[to]) dfs1(to);

}

top.push_back(v);

}

void dfs2(int v, int c)

{

int i, to;

color[v] = c;

for(i = 0; i < gr[v].size(); i++)

{

to = gr[v][i];

if (color[to] == -1) dfs2(to,c);

}

}

int main(void)

{

scanf("%d %d",&n,&m);

g.assign(n+1,vector<int>());

gr.assign(n+1,vector<int>());

for(i = 0; i < m; i++)

{

scanf("%d %d",&a,&b);

g[a].push_back(b); gr[b].push_back(a);

}

used.assign(n+1,0);

for(i = 1; i <= n; i++)

if (!used[i]) dfs1(i);

color.assign(n+1,-1);

for(c = 0, i = 1; i <= n; i++)

{

v = top[n-i];

if (color[v] == -1) dfs2(v,c++);

}

used.assign(c,1);

for(i = 1; i < g.size(); i++)

for(j = 0; j < g[i].size(); j++)

{

to = g[i][j];

// check edge i -> j if they in the same scc.

if (color[i] != color[to]) used[color[i]] = 0;

}

for(c = i = 0; i < used.size(); i++)

if (used[i]) c++;

if (c > 1) res = 0;

else

{

for(i = 0; i < used.size(); i++)

if (used[i]) col = i;

for(i = 0; i < color.size(); i++)

if (color[i] == col) res++;

}

printf("%d\n",res);

if (res > 0)

for(i = 0; i < color.size(); i++)

if (color[i] == col) printf("%d ",i);

printf("\n");

return 0;

}