首页 > 代码库 > POJ 2553 taarjan缩点+度数

POJ 2553 taarjan缩点+度数

2024-07-25 16:50:06   223人阅读

The Bottom of a Graph
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 8904 Accepted: 3689

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 31 3 2 3 3 12 11 20

Sample Output

1 32


题目意思：
给一个n个结点，m条边的有向图，若一个点所能到达的其他点都能到达该点或一个点不能到达其他点，那么该点为sink，从小到达输出sink。


思路：
这个题难在翻译上，特别是我这四级考了两次才过的人T-T，看懂了就很水了，先用tarjan缩点分块，然后求出没有出度的块的点标记下来，最后排序输出就行了。


代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 #include <queue> 7 #include <stack> 8 using namespace std; 9 10 #define N 500511 int n, m;12 vector<int>ve[N];13 int low[N], dfn[N], dfn_clock;14 int in[N], out[N], instack[N], a[N], b[N];15 int cnt;16 stack<int>st;17 18 void init(){19     int i, j;20     while(!st.empty()) st.pop();21     22     for(i=0;i<=n;i++){23         ve[i].clear();instack[i]=1;24     }25     memset(dfn,0,sizeof(dfn));26     memset(in,0,sizeof(in));27     memset(out,0,sizeof(out));28 }29 30 void tarjan(int u){31     int i, j, v;32     dfn[u]=low[u]=dfn_clock++;33     st.push(u);34     for(i=0;i<ve[u].size();i++){35         v=ve[u][i];36         if(!dfn[v]){37             tarjan(v);38             low[u]=min(low[u],low[v]);39         }40         else if(instack[v]){41             low[u]=min(low[u],dfn[v]);42         }43     }44     if(low[u]==dfn[u]){45         cnt++;46         while(1){47             v=st.top();st.pop();48             a[v]=cnt;instack[v]=0;49             if(v==u) break;50         }51     }52 }53 54 main()55 {56     int i, j, k;57     int x, y;58     while(scanf("%d",&n)==1&&n){59         scanf("%d",&m);60         init();61         while(m--){62             scanf("%d %d",&x,&y);63             ve[x].push_back(y);64         }65         dfn_clock=1;cnt=0;66         for(i=1;i<=n;i++){67             if(!dfn[i])68             tarjan(i);69         }70         for(i=1;i<=n;i++){71             for(j=0;j<ve[i].size();j++){72                 x=ve[i][j];73                 if(a[x]!=a[i]){74                     out[a[i]]++;in[a[x]]++;75                 }76             }77         }78         k=0;79         for(i=1;i<=n;i++){80             if(!out[a[i]]){81                 b[k++]=i;82             }83         }84         sort(b,b+k);85         printf("%d",b[0]);86         for(i=1;i<k;i++) printf(" %d",b[i]);87         cout<<endl;88     }89 }

 

POJ 2553 taarjan缩点+度数


联系
我们