大致题意:
给出一个有向图,求图中是否存只在一个入度为0的强联通分量,存在的话输出这个分量中的所有点。否则只输出一个 0.
大致思路:
Tarjan缩点,后对所有强连通分量求出入度出度~~
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=3015;
const int mMax=5001000;
class edge{
public:
int v,nex;
};edge e[mMax];
int k,head[nMax];//head[i]是以点i为起点的链表头部
void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b
e[k].v=b;
e[k].nex=head[a];
head[a]=k;k++;
}
int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep; //atype 强连通分量的个数
bool insta[nMax];
void Tarjan(int u){ //我的Tarjan模版
int i,j;
dfn[u]=low[u]=++dep;
sta[++top]=u;
insta[u]=1;
for(i=head[u];i;i=e[i].nex){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else{
if(insta[v])low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
atype++; //强连通分量个数
do{
j=sta[top--];
belon[j]=atype; //第j个点属于第type个连通块
insta[j]=0;
}while(u!=j);
}
}
int out[nMax]; //每个连通块的出度
int in[nMax];
void init(){
k=1;
dep=1;
top=atype=0;
memset(insta,0,sizeof(insta)); //是否在栈中
memset(head,0,sizeof(head)); //静态链表头指针
memset(low,0,sizeof(low)); //Tarjan的low数组
memset(dfn,0,sizeof(dfn)); //Tarjan的dfn数组
memset(out,0,sizeof(out)); //记录每个强连通分量的出度
memset(in,0,sizeof(in)); //记录每个强连通分量的入度
memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
}
int main(){
int t,n,m,i,j,a,b,tmp,sum,inum,onum;
while(scanf("%d",&n)!=EOF){
init();
inum=onum=0;
for(i=1;i<=n;i++){
while(scanf("%d",&m)&&m){
addedge(i,m);
}
}
for(i=1;i<=n;i++){
if(!dfn[i])Tarjan(i);
}
for(i=1;i<=n;i++){
tmp=belon[i];
for(j=head[i];j;j=e[j].nex){
int v=e[j].v;
if(belon[i]!=belon[v]){
out[tmp]++;
in[belon[v]]++;
}
}
}
for(i=1;i<=atype;i++){
if(in[i]==0){
tmp=i;
inum++;
}
}
if(inum!=1){
printf("0\n");
}
else{
for(i=1;i<=n;i++){
if(belon[i]==tmp){
printf("%d ",i);
}
}
printf("0\n");
}
}
return 0;
}
分享到:
相关推荐
)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...
"有向图的强连通分量(scc)Tarjan算法" Tarjan算法是基于深度优先搜索的算法,...Tarjan算法是解决有向图强连通分量问题的有效算法,具有快速、准确的特点,广泛应用于网络拓扑结构、社交网络分析、数据挖掘等领域。
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
使用Tarjan算法进行快速计算强连通分量,C++语言实现。
通过以上步骤,Tarjan算法可以有效地找到有向图中的所有强连通分量。这种算法的时间复杂度为O(V+E),其中V是顶点数,E是边数,因为每个顶点和每条边最多被访问一次。因此,即使在大规模图中,Tarjan算法也能保持较好...
Tarjan求有向图的强连通分量, */ #include #include #include #include #include using namespace std; const int MAXN = 1e5 + 10; struct Edge{ int to, next, dis; }edge[MAXN << 1];
而强连通分量则是有向图中的一个子集,其中的每个顶点都可以通过有向边到达其他任何顶点,同时其他任何顶点也能到达这个子集中的每一个顶点。换句话说,强连通分量是最小的强连通子图。 检测强连通分量通常采用深度...
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
4. **强连通分量**:在有向图中,如果存在从节点u到节点v的路径,同时也存在从节点v到节点u的路径,那么称u和v是强连接的。强连通分量是指图中任意两个节点都是强连接的子图。Kosaraju算法和Tarjan算法常用于检测强...
在有向图中,如果从节点A到节点B存在一条有向路径,并且从节点B到节点A也存在一条有向路径,则节点A和节点B属于同一个强连通分量。 以下是使用C语言实现查找强连通分量的示例代码,基于深度优先搜索(DFS)算法和...
纯代码
强连通分量是图论中的一个核心概念,主要应用于有向图中,是指图中的一个子图,其中的任意两个顶点都是相互可达的。在日常的图处理中,我们经常需要识别出这种子图结构,以便更好地分析网络拓扑或者数据流。了解和...
通过以上步骤,Tarjan算法可以有效地找到有向图中的所有强连通分量。这个过程通过深度优先搜索确保了对强连通分量的完整识别,同时利用堆栈保存了搜索状态,使得算法在实际应用中表现出较高的效率。 总的来说,...
Tarjan算法是由Robert Tarjan在1972年提出的,用于高效地找出有向图中的所有强连通分量。该算法的时间复杂度为 O(N + M),其中 N 是顶点数,M 是边的数量。相比于直接基于定义的方法(时间复杂度 O(N^2 + M)),...
这个模板提供了完整的有向图强连通分量求解流程,包括添加边、进行深度优先搜索、识别强连通分量、缩点以及构建新图。通过这个模板,可以方便地在实际问题中应用Tarjan算法解决有向图的强连通分量问题。在使用时,...
通过Tarjan算法,我们可以有效地找出有向图中的强连通分量,并且可以在过程中实现缩点,降低图的复杂度,这对于理解和分析复杂网络结构非常有用,如在数据流分析、网络路由、任务调度等领域都有应用。 总结来说,...
3. ** Tarjan's 强连通分量算法**:此算法不仅能检测有向图中的回路,还能找到所有的强连通分量,即图中任何两个顶点之间都存在双向路径的子图。该算法基于DFS,通过使用深度优先搜索树上的低点和编号来找到回路。 ...