首页 > 代码库 > POJ 2553 The Bottom of a Graph

POJ 2553 The Bottom of a Graph

2024-08-30 05:43:35   220人阅读

 
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 10687 Accepted: 4403

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. ThenG=(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+1is 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 31 3 2 3 3 12 11 20

Sample Output

1 32

Source

Ulm Local 2003
 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<vector> 5 #include<algorithm>  6 #include<stack> 7 #define maxm 500010 8 #define maxn 5010 9 using namespace std;10 int T,n,m;11 struct edge{12     int u,v,next;13 }e[maxm],ee[maxm];14 vector<int> kp[maxn],ans;15 int head[maxn],js,headd[maxn],jss;16 bool exist[maxn];17 int visx,cur;// cur--缩出的点的数量 18 int dfn[maxn],low[maxn],belong[maxn],chudu[maxn];19 stack<int>st;20 void init(){21     memset(chudu,0,sizeof(chudu));22     memset(e,0,sizeof(e));memset(ee,0,sizeof(ee));23     memset(head,0,sizeof(head));memset(headd,0,sizeof(headd));24     jss=js=visx=cur=0;25     memset(exist,false,sizeof(exist));26     while(!st.empty())st.pop();27     memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));28     memset(belong,0,sizeof(belong));29     ans.resize(0);30     for(int i=0;i<maxn;i++)kp[i].resize(0);31 }32 void add_edge1(int u,int v){33     e[++js].u=u;e[js].v=v;34     e[js].next=head[u];head[u]=js;35 }36 void tarjan(int u){37     dfn[u]=low[u]=++visx;38     exist[u]=true;39     st.push(u);40     for(int i=head[u];i;i=e[i].next){41         int v=e[i].v;42         if(dfn[v]==0){43             tarjan(v);44             low[u]=min(low[u],low[v]);45         }46         else if(exist[v]&&low[u]>dfn[v]) low[u]=dfn[v];47     }48     int j; 49     if(low[u]==dfn[u]){50         ++cur;51         do{52             j=st.top();st.pop();exist[j]=false;53             kp[cur].push_back(j);54             belong[j]=cur;55         }while(j!=u);56     }57 }58 void add_edge2(int u,int v){59     ee[++jss].u=u;ee[jss].v=v;60     ee[jss].next=headd[u];headd[u]=jss;61 }62 void apki(int x){63     for(int i=0;i<kp[x].size();i++){64         int k=kp[x][i];65         ans.push_back(k);66     }67 }68 int main()69 {70     while(scanf("%d%d",&n,&m)==2){71         init();72         int u,v;73         for(int i=0;i<m;i++){74             scanf("%d%d",&u,&v);add_edge1(u,v);75         }76         for(int i=1;i<=n;i++){// 求强连通分量77             if(dfn[i]==0) tarjan(i);78         }79         for(int i=1;i<=m;i++){80             int u=e[i].u,v=e[i].v;81             if(belong[u]!=belong[v]){82                 add_edge2(belong[u],belong[v]);83                 chudu[belong[u]]++;84             }85         }86         for(int i=1;i<=cur;i++){87             if(chudu[i]==0)88               apki(i);89         }90         sort(ans.begin(),ans.end());91         for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);92         printf("\n");93     }94     return 0;95 }

 思路：和POJ2762差不很多

POJ 2553 The Bottom of a Graph


联系
我们