首页 > 代码库 > POJ 2553 The Bottom of a Graph
POJ 2553 The Bottom of a Graph
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.
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。