The Bottom of a Graph
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 8636 | Accepted: 3582 |
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=(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.
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.
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.
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
传送门：【POJ】The Bottom of a Graph
题目大意：给一个有向图，问出度为0的点的集合（将相互可达的点看成一个点，如果该点是出度为0，则该点所包括的所有点都算出度为0的点）。
题目分析：强连通缩点。然后对所有点按编号从小到大扫描，如果所属的分量出度为0，输出。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define clear( a , x ) memset ( a , x , sizeof a )
const int MAXN = 5001 ;
const int MAXE = 100000 ;
struct Edge {
int v , n ;
Edge ( int var = 0 , int next = 0 ) : v(var) , n(next) {}
} ;
struct SCC {
Edge edge[MAXE] ;
int adj[MAXN] , cntE ;
int Dfn[MAXN] , Low[MAXN] , dfs_clock ;
int scc[MAXN] , scc_cnt ;
int S[MAXN] , top ;
bool ins[MAXN] ;
bool ou[MAXN] ;
void init () {
top = 0 ;
cntE = 0 ;
scc_cnt = 0 ;
dfs_clock = 0 ;
clear ( ou , 0 ) ;
clear ( ins , 0 ) ;
clear ( Dfn , 0 ) ;
clear ( adj , -1 ) ;
}
void addedge ( int u , int v ) {
edge[cntE] = Edge ( v , adj[u] ) ;
adj[u] = cntE ++ ;
}
void Tarjan ( int u ) {
Dfn[u] = Low[u] = ++ dfs_clock ;
S[top ++] = u ;
ins[u] = 1 ;
for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
int v = edge[i].v ;
if ( !Dfn[v] ) {
Tarjan ( v ) ;
Low[u] = min ( Low[u] , Low[v] ) ;
}
else if ( ins[v] )
Low[u] = min ( Low[u] , Dfn[v] ) ;
}
if ( Low[u] == Dfn[u] ) {
++ scc_cnt ;
while ( 1 ) {
int v = S[-- top] ;
ins[v] = 0 ;
scc[v] = scc_cnt ;
if ( v == u )
break ;
}
}
}
void find_scc ( int n ) {
REPF ( i , 1 , n )
if ( !Dfn[i] )
Tarjan ( i ) ;
}
void solve ( int n ) {
REPF ( u , 1 , n )
for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
int v = edge[i].v ;
if ( scc[u] != scc[v] ) {
ou[scc[u]] = 1 ;
}
}
int flag = 0 ;
REPF ( i , 1 , n )
if ( !ou[scc[i]] ) {
if ( flag )
printf ( " " ) ;
flag = 1 ;
printf ( "%d" , i ) ;
}
printf ( "\n" ) ;
}
} ;
SCC C ;
void work () {
int n , m ;
int u , v ;
while ( ~scanf ( "%d%d" , &n , &m ) && n ) {
C.init () ;
while ( m -- ) {
scanf ( "%d%d" , &u , &v ) ;
C.addedge ( u , v ) ;
}
C.find_scc ( n ) ;
C.solve ( n ) ;
}
}
int main () {
work () ;
return 0 ;
}