1799. BOTTOM - The Bottom of a Graph

 

We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. Then G = (V,E) is called a directed graph.

Let n be a positive integer, and let p = (e1,..., en) be a sequence of length n of edges ei Î E such that ei = (vi, vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→ vn+1).

Here are some new definitions. A node v in a graph G = (V, E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e.

bottom(G) = {v Î V| "w Î V: (v → w) Þ (w → v)}

You have to calculate the bottom of certain graphs.

 

Input. The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G = (V, E), where the vertices will be identified by the integer numbers in the set V = {1, ..., v}. You may assume that 1 ≤ v ≤ 5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1, w1, ..., ve, we with the meaning that (vi, wi) Î E. There are no edges other than specified by these pairs. The last test case is followed by a zero.

 

Output. For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.

 

Sample Input

3 3

1 3 2 3 3 1

2 1

1 2

0

 

Sample Output

1 3

2

 

 

РЕШЕНИЕ

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

 

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

Выделим в графе компоненты сильной связности. Пусть v – сток. Тогда из ССК (сильно связной компоненты), в которой лежит v, не должны выходить ребра в другие ССК. Если предположить обратное – то есть что существует путь v → w, где v и w лежат в разных ССК, то обратного пути из w в v не существует (иначе v и w лежали бы в одной ССК).

Ищем ССК, из которых нет исходящих ребер в другие ССК. Выводим все вершины таких ССК.

 

Пример

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

 

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

 

#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, flag, to, c;

 

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)

{

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

  {

    g.assign(n+1,0);gr.assign(n+1,0);

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

    {

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

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

    }

    top.clear(); 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];

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

    }

 

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

      if(used[color[i]])

      {

        if (flag) printf(" ");

        printf("%d",i); flag = 1;

      }

    printf("\n");

  }

  return 0;

}