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.
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，對於圖中每個能到達它的頂點w，w亦可到達v，當然，如果v不能到達其他頂點，這樣的v也是滿足條件的。 解題思路：先用tarjan縮點，然後統計出出度為 0 的頂點即可。 請看代碼：
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 5005 ;
vector<int> vert[MAXN] ;
vector<int> f[MAXN] ; // 統計每個強連通分量所包含的頂點
set<int> ans ; // 記錄滿足條件的點，set 中的元素默認是從小到大排序的
int n , m ;
bool vis[MAXN] ;
int dfn[MAXN] ;
int low[MAXN] ;
int id[MAXN] ;
int d[MAXN] ; // 統計每個強連通分量的出度
int stap[MAXN] ;
int top ;
bool inq[MAXN] ;
int tmpdfn ;
int fz ;
void clr()
{
ans.clear() ;
mem(vis , 0) ;
mem(dfn , 0) ;
mem(low , 0) ;
mem(id , -1) ;
mem(d , 0) ;
mem(inq , 0) ;
mem(stap , -1) ;
tmpdfn = 0 ;
top = -1 ;
fz = 0 ;
int i ;
for(i = 1 ; i <= n ; i ++)
{
vert[i].clear() ;
f[i].clear() ;
}
}
void tarjan(int u)
{
vis[u] = 1 ;
stap[++ top] = u ;
inq[u] = 1 ;
dfn[u] = low[u] = ++ tmpdfn ;
int i ;
for(i = 0 ; i < vert[u].size() ; i ++)
{
int v = vert[u][i] ;
if(!vis[v])
{
tarjan(v) ;
low[u] = min(low[u] , low[v]) ;
}
else if(inq[v])
{
low[u] = min(low[u] , dfn[v]) ;
}
}
if(low[u] == dfn[u])
{
fz ++ ;
int tmp ;
do
{
tmp = stap[top --] ;
id[tmp] = fz ;
f[fz].push_back(tmp) ;
inq[tmp] = false ;
}while (tmp != u) ;
}
}
void init()
{
clr() ;
int i ;
for(i = 0 ; i < m ; i ++)
{
int a , b ;
scanf("%d%d" , &a , &b) ;
vert[a].push_back(b) ;
}
}
void solve()
{
int i ;
for(i = 1 ; i <= n ; i ++)
{
if(!vis[i])
tarjan(i) ;
}
int j ;
for(i = 1 ; i <= n ; i ++)
{
for(j = 0 ; j < vert[i].size() ; j ++)
{
int x , y ;
x = id[i] ;
y = id[ vert[i][j] ] ;
if(x != y)
{
d[x] ++ ;
}
}
}
for(i = 1 ; i <= fz ; i ++)
{
if(d[i] == 0)
{
for(j = 0 ; j < f[i].size() ; j ++)
{
ans.insert(f[i][j]) ;
}
}
}
set<int> :: iterator it ;
int sum = 0 ;
for(it = ans.begin() ; it != ans.end() ; ++ it)
{
printf("%d" , *it) ;
if(sum < ans.size() - 1)
putchar(' ') ;
sum ++ ;
}
puts("") ;
}
int main()
{
while (scanf("%d" , &n) != EOF)
{
if(n == 0)
break ;
scanf("%d" , &m) ;
init() ;
solve() ;
}
return 0 ;
}
</SPAN>
