The Bottom of a Graph（tarjan + 缩点）

The Bottom of a Graph

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 9139		Accepted: 3794

Description

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=(e₁,...,e_n) be a sequence of length n of edges e_i∈E such that e_i=(v_i,v_i+1) for a sequence of vertices (v₁,...,v_n+1). Then p is called a path from vertex v₁ to vertex v_n+1in G and we say that v_n+1 is reachable from v₁, writing (v₁→v_n+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 v₁,w₁,...,v_e,w_e with the meaning that (v_i,w_i)∈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

Source

Ulm Local 2003

参考代码这里：http://blog.****.net/ehi11/article/details/7884851

缩点：（这个概念也是看了别人的理解）先求有向图的强连通分量 ， 如果几个点同属于一个强连通 ， 那就给它们标上相同的记号 ， 这样这几个点的集合就形成了一个缩点。

题目大意：求出度为0的强连通分量

 #include<stdio.h>
 #include<queue>
 #include<string.h>
 using namespace std;
 const int M =  ;
 int n , m ;
 int stack [M] , top =  , index = ;
 bool instack [M] ;
 int dfn[M] , low[M] ;
 int cnt =  ;
 vector <int> e[M] ;
 int belong[M] ;
 int out[M] ;

 void init (int n)
 {
     top =  ;
     cnt =  ;
     index =  ;
     memset (stack , - , sizeof(stack)) ;
     memset (instack ,  , sizeof(instack)) ;
     memset (dfn , - , sizeof(dfn)) ;
     memset (low , - , sizeof(low)) ;
     for (int i =  ; i <= n ; i++)
         e[i].clear () ;
     memset (belong , - , sizeof(belong)) ;
     memset (out ,  , sizeof(out)) ;
 }

 void tarjan (int u)
 {
     int v ;
     dfn[u] = low[u] = index++ ;
     instack[u] = true ;
     stack[++top] = u ;
     for (int i =  ; i < e[u].size () ; i++) {
         v = e[u][i] ;
         if (dfn[v] == -) {
             tarjan (v) ;
             low[u] = min (low[u] , low[v]) ;
         }
         else if (instack[v])
             low[u] = min (low[u] , dfn[v]) ;
     }
     if (low[u] == dfn[u]) {
         cnt++ ;
         do {
             v = stack[top--] ;
             instack[v] = false ;
             belong[v] = cnt ;
         } while (u != v) ;
     }
 }

 int main ()
 {
    //freopen ("a.txt" , "r" , stdin) ;
     int u , v ;
     while (~ scanf ("%d" ,&n)) {
         if (n == )
             break ;
         init (n) ;
         scanf ("%d" , &m) ;
         while (m--) {
             scanf ("%d%d" , &u , &v) ;
             e[u].push_back (v) ;
         }
         for (int i =  ; i <= n ; i++) {
             if (dfn[i] == -)
                 tarjan (i) ;
         }
         for (int i =  ; i <= n ; i++) {
             for (int j =  ; j < e[i].size () ; j++) {
                 if (belong [i] != belong[e[i][j]])
                     out[belong[i]] ++;
             }
         }
         int k =  ;
         for (int i =  ; i <= n ; i++) {
             if (out[belong[i]] == ) {
                 if (k++)
                     printf (" ") ;
                 printf ("%d" , i) ;
             }
         }
         puts ("") ;
     }
     return  ;
 }