本文主要是介绍poj 2553 The Bottom of a Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意 若节点V所能到达的点{w}，都能反过来到达v，那我们称v是sink。
强连通+缩点
就是求极大连通分量，最后统计出度为0的点，排序后输出初度为0的分量包含的每一个点。
不管怎么样都会存在一个出度为0的点，所以说If the bottom is empty, print empty line是没有用的。
看了我半天的题目，出题的真是个2货。。。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
const int size = 10010;
vector<int> edge[size];
int stack[size],low[size],dfn[size],ins[size],out[size],belong[size],ans[size];
int tdfn,flag,tot,top,type,v,e,start,end;
void tarjan(int s)
{
dfn[s]=low[s]=++tdfn;
stack[++top]=s;
ins[s]=1;
int t;
for(int i=0;i<edge[s].size();i++)
{
t=edge[s][i];
if(!dfn[t])
{
tarjan(t);
if(low[t]<low[s]) low[s]=low[t];
}
else if(ins[t])
{
if(low[s]>dfn[t]) low[s]=dfn[t];
}
}
if(dfn[s]==low[s])
{
type++;
do{
t=stack[top--];
ins[t]=0;
belong[t]=type;
}while(s!=t);
}
}
int main()
{
while(scanf("%d",&v)&&v)
{
scanf("%d",&e);
memset(ins,0,sizeof(ins));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(out,0,sizeof(out));
tdfn=flag=tot=top=type=0;
memset(belong,0,sizeof(belong));
for(int i=0;i<=v;i++)
edge[i].clear();
for(int i=0;i<e;i++)
{
scanf("%d%d",&start,&end);
edge[start].push_back(end);
}
for(int i=1;i<=v;i++)
{
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=v;i++)
{
for(int j=0;j<edge[i].size();j++)
{
if(belong[i]!=belong[edge[i][j]])
out[belong[i]]++;
}
}
for(int i=1;i<=type;i++)
{
if(out[i]==0)
{
for(int j=1;j<=v;j++)
{
if(belong[j]==i)
{
ans[tot++]=j;
}
}
}
}
sort(ans,ans+tot);
for(int i=0;i<tot-1;i++)
{
printf("%d ",ans[i]);
}
printf("%d\n",ans[tot-1]);
}
return 0;
}这篇关于poj 2553 The Bottom of a Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
