The Bottom of a Graph Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 11623 Accepted: 4784 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
Ulm Local 2003
题意：n个点，m条边，让你找到缩点之后出度为0的节点， 然后将节点编号从小到大排序输出。 分析： Tarjan缩点预处理，用个vector把缩过点的集合保存下来，接下来对每一点判断其是否有出度(注意判断同一个缩点内不算出度)，最后将出度为0的缩点集合排序输出就行；
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> using namespace std; typedef long long LL; const int MAXN = 5010; int head[MAXN], stack[MAXN], col[MAXN], vis[MAXN]; int dfn[MAXN], low[MAXN], out[MAXN], a[MAXN]; int index, top, scc, cnt; vector<int> G[MAXN]; struct edge { int to; int next; }edge[MAXN << 3]; void add_edge(int u, int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } inline void tarjan(int u) { int v; low[u] = dfn[u] = ++index; stack[top++] = u; vis[u] = 1; for(int i = head[u]; ~i; i = edge[i].next) { v = edge[i].to; if(!dfn[v]) { tarjan(v); low[u] = min(low[v], low[u]); } else if(vis[v] && low[u] > dfn[v]) { low[u] = dfn[v]; } } if(low[u] == dfn[u]) { scc++; do { v = stack[--top]; vis[v] = 0; col[v] = scc; //染色 G[scc].push_back(v); //缩点 } while(v != u); } } void solve(int n) { memset(dfn, 0, sizeof(dfn)); memset(vis, 0, sizeof(vis)); memset(out, 0, sizeof(out)); memset(a, 0, sizeof(a)); for(int i = 0; i < MAXN; i++) { G[i].clear(); } index = scc = top = 0; for(int i = 1; i <= n; ++i) { if(!dfn[i]) { tarjan(i); } } // for(int i = 1; i <= n; i++) { // printf("%d -> %d\n", i, col[i]); // } for(int i = 1; i <= n; ++i) { for(int j = head[i]; ~j; j = edge[j].next) { if(col[i] != col[edge[j].to]) { //同一个缩点内不算出度 out[col[i]]++; } } } int p = 0; for(int i = 1; i <= scc; ++i) { if(out[i]) continue; for(int j = 0; j < G[i].size(); ++j) { a[p++] = G[i][j]; } } sort(a, a + p); for(int i = 0; i < p; ++i) { if(i) printf(" "); printf("%d", a[i]); } printf("\n"); } int main() { int n, m, A, B; while(scanf("%d", &n) && n) { memset(head, -1, sizeof(head)); cnt = 0; scanf("%d", &m); while(m--) { scanf("%d %d", &A, &B); add_edge(A, B); } solve(n); } return 0; }