1937. Fire safety

 

There are n houses in the city of Zelenograd. Some of them are connected by one-way roads.

In recent times in Zelenograd the incidents of fires have increased. In this regard, the residents decided to build several fire stations in the city. But there was a problem – the fire engine traveling on the call, of course, can ignore the direction of the current road, however, the car returning from the job is obliged to follow the traffic rules (the people of Zelenograd piously respect these rules!).

It is clear that wherever the fire truck will be, it should be possible to return to the fire station where from it started its way. But the construction of stations costs a lot of money, so at the city council it was decided to build a minimum number of stations in such a way that this condition was hold. In addition for saving money, it was decided to build stations in the form of extensions to existing houses.

Your task is to write a program that calculates the optimal position of the stations.

 

Input. First line contains the number of houses n (1 ≤ n ≤ 3000). Second line contains the number of roads m (1 ≤ m ≤ 105). Then the description of the roads is given in format ai bi meaning that it is allowed for the cars to move along the road i from the house ai to the house bi (1 ≤ ai, bi ≤ n).

 

Output. In the first line print the minimum number of fire stations k that must be built. In the second line print k numbers in random order – the houses where you need to attach the fire stations. If there are several optimal solutions, output any.

 

Sample input

Sample output

 
5
7
1 2
2 3
3 1
2 1
2 3
3 4

2 5

2

4 5

 

 

SOLUTION

graphs – strongly connected components

 

Algorithm analysis

In this problem you need to find the minimum set of vertices reachable from all other vertices in the graph. Find the condensation of the graph. Consider a strongly connected component without any outgoing edge. Having arrived from other components, you can put out the fire, but you will no longer be able to get home by following the road rules. Therefore, if there are no outgoing edges from some connected component, then it is necessary to build a fire station in it. There is no need to build other stations, since from any vertex it is always possible to get along the edges of the graph into a component without outgoing edges.

 

Example

The input graph contains three strongly connected components. No edge comes out from components consisting of one vertex (4 and 5). Therefore, it is enough to build fire stations in them.

 

Algorithm realization

The input graph is stored in the adjacency list g. The reversed graph (the graph in which all edge directions are reversed) is stored in the adjacency list gr.

 

vector<vector<int> > g, gr;

vector<int> used, top, color, repr;

 

The function dfs1 implements depth first search on the input graph. In the array top store the vertices in the order in which the depth first search ends their processing.

 

void dfs1(int v)

{

  used[v] = 1;

  for (int to : g[v])

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

  top.push_back(v);

}

 

The function dfs2 implements depth first search on the reversed graph. All vertices that will be traversed as a result of a recursive call of dfs2 function belong to one strongly connected component. Color all the visited vertices with color c. Vertices in one strongly connected component have the same color. For each color ñ memoize in the array repr its representative – any vertex colored with color ñ.

 

void dfs2(int v, int c)

{

  color[v] = c;

  repr[c] = v;

  for (int to : gr[v])

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

}

 

The main part of the program. Read the input data. Build the reversed graph.

 

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

g.resize(n+1);

gr.resize(n+1);

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

{

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

  g[a].push_back(b);

  gr[b].push_back(a);

}

 

Start the depth first search on the input graph. The sequence in which the graph vertices processing is completed is stored in the array top.

 

used.resize(n+1);

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

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

 

Start the depth first search on the reversed graph. Iterate the vertices of the reversed graph in the order of traversing the array top from right to left (from end to start). For convenience of the further processing, let’s reverse the array top.

 

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

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

reverse(top.begin(), top.end());

 

The vertices included in one strongly connected component are colored with the same color. The current color is in the variable c.

 

c = 0;

for (int v : top)

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

 

The variable c contains the number of strongly connected components.

 

used.assign(c, 1);

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

  for (int to : g[i])

 

Iterate over the edges of the graph (i, to). Check if the vertices i and to lie in different strongly connected components. This is the case if they are colored in different colors. In this case there is no sense to build a fire station in the connected component with color color[i], so set used[color[i]] = 0.

 

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

}

 

Count the number of components c where the fire station should be built.

 

c = 0;

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

  if (used[i]) c++;

 

Print the number of fire stations c that must be built.

 

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

 

For each component of color i, that does not have any outgoing edge, print one of its representatives (the value of repr[i]) – these will be the numbers of houses near which fire stations should be built.

 

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

  if (used[i]) printf("%d ",repr[i]);

printf("\n");