本文主要是介绍csu 1526: Beam me out!（强连通分量 Tarjan），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
从1开始的所有路径 是否都能到达n 所用的步数是否是无限的
1）判断n是否可达
2）判断是否有环
3）判断是否所有的点都可以从1开始可达
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;void read(int &x)
{char ch;x=0;while(ch=getchar(),ch!=' '&&ch!='\n'){x=x*10+ch-'0';}
}const int MAXN=50010;
const int MAXM=5000010;
//判断是否有环 是否可达n
struct Edge
{int to,next;
}edge[MAXM];
int head[MAXN],tot;
int low[MAXN],dfn[MAXN],sta[MAXN],belong[MAXN];
int Index,top;
int scc;
int instack[MAXN];
int cirflag,canreach;
int n,m;
int cd[MAXN];void addedge(int u,int v)
{edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++;
}void Tarjan(int u)
{if(u==n) canreach=1;int v;low[u]=dfn[u]=++Index;sta[top++]=u;instack[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){v=edge[i].to;if(u==v) cirflag=1;if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}else if(instack[v])low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){scc++;do{v=sta[--top];instack[v]=0;belong[v]=scc;}while(v!=u);}
}void solve()
{MEM(dfn,0);MEM(instack,0);MEM(cd,0);Index=scc=top=cirflag=canreach=0;Tarjan(1);for(int i=1;i<=n;i++){for(int j=head[i];j!=-1;j=edge[j].next){int k=edge[j].to;int u=belong[i];int v=belong[k];if(u!=v){cd[u]++;}}}int cnt=0;for(int i=1;i<=scc;i++)if(cd[i]==0)cnt++;int sum=0;for(int i=1;i<=n;i++){if(dfn[i]!=0)sum++;}if(sum!=scc)//判断是不是所有的点都在联通分量里面cirflag=1;if(cnt==1&&canreach)printf("PARDON ");else printf("PRISON ");if(!cirflag) puts("LIMITED");else puts("UNLIMITED");
}void init()
{tot=0;MEM(head,-1);
}int main()
{
// fread;
// int n;while(scanf("%d",&n)!=EOF){init();
// int m;for(int i=1;i<n;i++){scanf("%d",&m);for(int j=0;j<m;j++){int v;scanf("%d",&v);addedge(i,v);}}solve();}return 0;
}
这篇关于csu 1526: Beam me out!（强连通分量 Tarjan）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
