POJ2553解题报告 强连通分支

The Bottom of a Graph

Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 4000 Accepted: 1637

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+1 in 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 我的tarjan第二题 题目所求：按升序输出出度为0的强连通分支所包含的点。 思路：先用tarjan算法标记各个强连通分支内的点，然后求出每个连通分支的出度，找出出度为0的强连通分支并标记该分支内的点，最后 按照顺序输出符合条件的每个点。。 #include<iostream> using namespace std; int S[6000],C,dfn[6000],low[6000],stack[6000],top,t; bool in[6000]; struct L { int v; L *next; }; L *head[6000]; void tarjan(int v) { dfn[v]=low[v]=++t; stack[top++]=v; in[v]=true; for(L *p=head[v];p!=NULL;p=p->next) if(!dfn[p->v]) { tarjan(p->v); if(low[p->v]<low[v]) low[v]=low[p->v]; } else if(in[p->v]&&low[p->v]<low[v]) low[v]=low[p->v]; if(dfn[v]==low[v]) { C++; do { v=stack[--top]; S[v]=C; in[v]=false; }while(dfn[v]!=low[v]); } } int main() { int n,m,i,a,b; while(cin>>n&&n&&cin>>m) { memset(head,0,sizeof(int)*6000); memset(S,0,sizeof(int)*6000); memset(dfn,0,sizeof(int)*6000); memset(low,0,sizeof(int)*6000); memset(in,0,sizeof(bool)*6000); for(i=0;i<m;i++) { cin>>a>>b; L *k=new L; k->next=head[a]; head[a]=k; k->v=b; } C=top=t=0; for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i); int chudu[6000]={0}; bool O[6000]={false}; for(i=1;i<=n;i++) for(L *p=head[i];p!=NULL;p=p->next) if(S[i]!=S[p->v]) chudu[S[i]]++; for(i=1;i<=C;i++) if(!chudu[i]) { for(a=1;a<=n;a++) if(S[a]==i) O[a]=true; } for(a=1;a<=n;a++) if(O[a]) cout<<a<<' '; cout<<endl; } return 0; }