12232

# poj2533 The Bottom of a Graph（Tarjan+缩点）

<table align="center"><tbody><tr><td>Time Limit: 3000MS</td> <td width="10px"> </td> <td>Memory Limit: 65536K</td> </tr><tr><td>Total Submissions: 12659</td> <td width="10px"> </td> <td>Accepted: 5211</td> </tr></tbody></table> <p class="pst">Description

We will use the following (standard) definitions from graph theory. Let <em>V</em> be a nonempty and finite set, its elements being called vertices (or nodes). Let <em>E</em> be a subset of the Cartesian product <em>V×V</em>, its elements being called edges. Then <em>G=(V,E)</em> is called a directed graph.
Let <em>n</em> be a positive integer, and let <em>p=(e<sub>1</sub>,...,e<sub>n</sub>)</em> be a sequence of length <em>n</em> of edges <em>e<sub>i</sub>∈E</em> such that <em>e<sub>i</sub>=(v<sub>i</sub>,v<sub>i+1</sub>)</em> for a sequence of vertices <em>(v<sub>1</sub>,...,v<sub>n+1</sub>)</em>. Then <em>p</em> is called a path from vertex <em>v<sub>1</sub></em> to vertex <em>v<sub>n+1</sub></em> in <em>G</em> and we say that <em>v<sub>n+1</sub></em> is reachable from <em>v<sub>1</sub></em>, writing <em>(v<sub>1</sub>→v<sub>n+1</sub>)</em>.
Here are some new definitions. A node <em>v</em> in a graph <em>G=(V,E)</em> is called a sink, if for every node <em>w</em> in <em>G</em> that is reachable from <em>v</em>, <em>v</em> is also reachable from <em>w</em>. The bottom of a graph is the subset of all nodes that are sinks, i.e., <em>bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}</em>. You have to calculate the bottom of certain graphs. <p class="pst">Input

The input contains several test cases, each of which corresponds to a directed graph <em>G</em>. Each test case starts with an integer number <em>v</em>, denoting the number of vertices of <em>G=(V,E)</em>, where the vertices will be identified by the integer numbers in the set <em>V={1,...,v}</em>. You may assume that <em>1<=v<=5000</em>. That is followed by a non-negative integer <em>e</em> and, thereafter, <em>e</em> pairs of vertex identifiers <em>v<sub>1</sub>,w<sub>1</sub>,...,v<sub>e</sub>,w<sub>e</sub></em> with the meaning that <em>(v<sub>i</sub>,w<sub>i</sub>)∈E</em>. There are no edges other than specified by these pairs. The last test case is followed by a zero. <p class="pst">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. <p class="pst">Sample Input

```3 3 1 3 2 3 3 1 2 1 1 2 0 ``` <p class="pst">Sample Output

```1 3 2 ``` <p class="pst">Source

Ulm Local 2003   题目大意 多组数据输入，v个点，e条边，接下来一行是e对有向边，v为0时输入结束 求解最底端的强连通分量，顺序输出   思路 用Tarjan算法先缩点，再判断哪些强连通分量的出度为0，升序输出这些强连通分量里面的点的编号   ``` 1 #include <cstdio> 2 #include <vector> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int N=5e3+5; 8 int low[N],dfn[N],Stack[N],belong[N],cdu[N]; 9 bool inStack[N]; 10 int n,m,tot,tag,top; 11 vector<int> g[N]; 12 vector<int> res; 13 14 void init(){ 15 top=tag=0; 16 memset(low,0,sizeof low); 17 memset(dfn,0,sizeof dfn); 18 memset(Stack,0,sizeof Stack); 19 memset(belong,0,sizeof belong); 20 memset(cdu,0,sizeof cdu); 21 memset(inStack,false,sizeof inStack); 22 res.clear(); 23 for(int i=0;i<N;i++){ 24 g[i].clear(); 25 } 26 } 27 28 void tarjan(int u){ 29 int v; 30 low[u]=dfn[u]=++tot; 31 Stack[++top]=u; 32 inStack[u]=true; 33 for(int i=0;i<g[u].size();i++){ 34 v=g[u][i]; 35 if(dfn[v]==0){ 36 tarjan(v); 37 low[u]=min(low[u],low[v]); 38 } 39 else if(inStack[v]==true){ 40 low[u]=min(low[u],dfn[v]); 41 } 42 } 43 if(dfn[u]==low[u]){ 44 tag++; 45 do{ 46 v=Stack[top--]; 47 inStack[v]=false; 48 belong[v]=tag; 49 }while(u!=v); 50 } 51 } 52 53 int main(){ 54 while(scanf("%d",&n),n){ 55 init(); 56 scanf("%d",&m); 57 for(int i=1;i<=m;i++){ 58 int x,y; 59 scanf("%d%d",&x,&y); 60 g[x].push_back(y); 61 } 62 for(int i=1;i<=n;i++){ 63 if(dfn[i]==0){ 64 tot=0; 65 tarjan(i); 66 } 67 } 68 for(int i=1;i<=n;i++){ 69 for(int j=0;j<g[i].size();j++){ 70 int x=g[i][j]; 71 if(belong[i]!=belong[x]){ 72 cdu[belong[i]]++; 73 } 74 } 75 } 76 // for(int i=1;i<=tag;i++){ 77 // printf("%d",i); 78 // for(int j=0;j<vec[i].size();j++){ 79 // printf(" %d",vec[i][j]); 80 // } 81 // printf("\n"); 82 // } 83 for(int i=1;i<=tag;i++){ 84 if(cdu[i]>0) continue; 85 for(int j=1;j<=n;j++){ 86 if(belong[j]==i){ 87 res.push_back(j); 88 } 89 } 90 } 91 sort(res.begin(),res.end()); 92 for(int i=0;i<res.size();i++){ 93 if(i) printf(" "); 94 printf("%d",res[i]); 95 } 96 printf("\n"); 97 } 98 }```