Language:
The Bottom of a Graph
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 3 1 3 2 3 3 1 2 1 1 2 0 Sample Output 1 3 2 Source |
Tarjen缩点统计出度。
#include<cstdio> #include<cstdlib> #include<algorithm> #include<functional> #include<cstring> #include<iostream> using namespace std; #define MAXN (5000+10) #define MAXM (1000000+10) int n,m,h[MAXN],t[MAXN],dfs[MAXN],tim,kind,s[MAXN],tot; bool b[MAXN]; int edge[MAXM],next[MAXM],pre[MAXN],size; int x[MAXM],y[MAXM],numk[MAXN]; void addedge(int u,int v) { edge[++size]=v; next[size]=pre[u]; pre[u]=size; } void tar(int u) { dfs[u]=t[u]=++tim;b[u]=1;s[++tot]=u; for (int p=pre[u];p;p=next[p]) { int &v=edge[p]; if (!b[v]) tar(v),dfs[u]=min(dfs[u],dfs[v]); else if (!h[v]) dfs[u]=min(dfs[u],t[v]); //保证指向祖先 } if (dfs[u]==t[u]) { kind++; while (s[tot]!=u) h[s[tot--]]=kind,numk[kind]++; h[s[tot--]]=kind;numk[kind]++; } } int outdegree[MAXN]; int main() { while (scanf("%d",&n)&&n) { scanf("%d",&m); tot=size=tim=kind=0; memset(h,0,sizeof(h)); memset(t,0,sizeof(t)); memset(dfs,0,sizeof(dfs)); memset(s,0,sizeof(s)); memset(pre,0,sizeof(pre)); memset(b,0,sizeof(b)); memset(numk,0,sizeof(numk)); memset(outdegree,0,sizeof(outdegree)); for (int i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); addedge(x[i],y[i]); } for (int i=1;i<=n;i++) if (!b[i]) tar(i); // for (int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl; for (int i=1;i<=m;i++) { if (h[x[i]]^h[y[i]]) outdegree[h[x[i]]]++; } /* int ans=0; for (int i=1;i<=kind;i++) if (!outdegree[i]) ans+=numk[i]; cout<<ans<<endl; */ bool flag=0; for (int i=1;i<=n;i++) if (!outdegree[h[i]]) { if (flag) printf(" ");else flag=1;printf("%d",i); } // cout<<ans<<endl; cout<<endl; } return 0; }