The Bottom of a Graph Poj 2553

牛客网

poj 2553

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

题意：

，一个点所能到达的任意一个点都能返回这个点，那么这个点称为bottom点，找出所有的bottom点。
读入：
第一行 v e（点数和边数）
第二行 具体边的方向
当读0时结束

题解：

先找到图中所有强连通图，强连通图内的每个点都是互通的，然后Tarjan缩点，得到新图，如果一个点没有出去的边（即出度为0，无须管入度），那么这个点就符合要求。因为我们要找互相能到达的点，这又是缩点后的图，一个点有出度，肯定不能再返回。
大致是这个意思，好好想想，这算是Tarjan的模板题
（读题太费劲了。。。）

代码：

#include<bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=5020;
vector<int>v[maxn];
int n,m,x,y,k,top,num,inf;
int pos[maxn],vis[maxn],low[maxn],dnf[maxn];
int ans[maxn],cnt[maxn],degree[maxn];
void init()
{
   
	k=0;
    top=0;
    num=0;
    for(int i=0;i<=n;i++)v[i].clear();
    mem(vis);
    mem(pos);
    mem(ans);
    mem(cnt);
    mem(dnf);
    mem(low);
    mem(degree);
} 
void tarjan(int u)
{
   
	dnf[u]=low[u]=++k;
	pos[++top]=u;
	vis[u]=1;
	for(int i=0;i<v[u].size();i++)
	{
   
		int to=v[u][i];
		if(!dnf[to])
		{
   
			tarjan(to);
			low[u]=min(low[u],low[to]);
		}
		else if(vis[to])low[u]=min(low[u],dnf[to]);
	}//以上为正常的tarjan求强连通分量 
	if(low[u]==dnf[u])
	{
   
		num++;
		while(1)
		{
   
			inf=pos[top--];//栈中最上面的点 
			ans[inf]=num;// 同一连通分量的点上相同的颜色，相当于缩点 
			vis[inf]=0;//
			if(inf==u)break;//遍历完后退出 
		}
	}
}
void dfs(int u)
{
   
	cnt[u]=ans[u];//给点标记，防止重复搜索 
	for(int i=0;i<v[u].size();i++)
	{
   
		int to=v[u][i];
		if(ans[u]!=ans[to])degree[ans[u]]++;//如果这个点有出度，值++ 
		if(!cnt[to])dfs(to);//如果指向的点没被搜索过 
	}
}
void solve()
{
   
	for(int i=1;i<=n;i++)
		if(!dnf[i])tarjan(i);//如果这个点还没走过 
	for(int i=1;i<=n;i++)
		if(!cnt[i])dfs(i);//如果这个点没被走过 
	bool flag=1;
	for(int i=1;i<=n;i++)
	{
   
		if(!degree[ans[i]])//判断这个点是否有出度 
		{
   
			if(flag)//这里主要是为了控制格式，第一个不带空格，后面带空格 
			{
   
				printf("%d",i);
				flag^=1;
			}
			else printf(" %d",i);
		}
	}
	cout<<endl; 
}
int main()
{
   
	while(cin>>n&&n)
	{
   
		cin>>m;
		init();//初始化所有数组与值 
		for(int i=0;i<m;i++)
		{
   
			
			cin>>x>>y;
			v[x].push_back(y);//生成邻接表 
		}
		solve();
	}
	return 0;
}

对了，牛客网和poj的这个题都不支持头文件，否则编译错误