[PTA] Strongly Connected Components
算法参考了网上资料（Tarjan算法），嫌麻烦并没有使用给出的函数指针。
#include
#include #define MaxVertices 10 /* maximum number of vertices */
typedef int Vertex; /* vertices are numbered from 0 to MaxVertices-1 */
typedef struct VNode *PtrToVNode;
struct VNode {Vertex Vert;PtrToVNode Next;
};
typedef struct GNode *Graph;
struct GNode {int NumOfVertices;int NumOfEdges;PtrToVNode *Array;
};Graph ReadG(); /* details omitted */void PrintV( Vertex V )
{printf("%d ", V);
}void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) );int main()
{
// freopen("test.txt","r",stdin);Graph G = ReadG();StronglyConnectedComponents( G, PrintV );return 0;
}PtrToVNode insert(PtrToVNode p,int x)
{p->Next=(PtrToVNode)malloc(sizeof(struct VNode));p=p->Next;p->Vert=x;p->Next=NULL;return p;
}Graph ReadG()
{//乱七八糟的指针操作真是报警了好嘛//就不能愉快地使用邻接矩阵吗//反正你们也不会看这里我就吐槽下 int i,j,m,n,x,y;scanf("%d%d",&m,&n); Graph p=(Graph)malloc(sizeof(struct GNode));PtrToVNode *rear=(PtrToVNode*)malloc(m*sizeof(struct VNode));p->Array=(PtrToVNode*)malloc(m*sizeof(struct VNode));p->NumOfVertices=m;p->NumOfEdges=n;for(i=0;iArray[i]=(PtrToVNode)malloc(sizeof(struct VNode));p->Array[i]->Next=NULL;}for(i=0;iArray[i];p->Array[i]=p->Array[i]->Next;tmp->Next=NULL;free(tmp);} return p;
}int visited[MaxVertices];//判断是否访问过该节点（是否在堆栈里）
int dfn[MaxVertices];//dfn[i]存储i是第几个访问的点（即访问次序）
int low[MaxVertices];//low[i]存储和i连接的数字中最早访问次序号
int path[MaxVertices];//堆栈
int flag[MaxVertices];//判断顶点是否已经输出 int index=0;//记录访问次数
int cnt=0;//记录堆栈当前元素个数 int min(int x,int y)
{return xNumOfVertices;i++){visited[i]=0;flag[i]=0;dfn[i]=low[i]=-1;}for(i=0;iNumOfVertices;i++){if(!flag[i])dfs(G,i);}
}void dfs(Graph G,int v)
{int i;low[v]=dfn[v]=index++;visited[v]=1;PtrToVNode p=G->Array[v];push(v);while(p){i=p->Vert;if(dfn[i]==-1){dfs(G,i);low[v]=min(low[v],low[i]);}else if(visited[i]){low[v]=min(low[v],dfn[i]);}p=p->Next;}if(dfn[v]==low[v]){int t;do{t=pop();visited[t]=0;flag[t]=1;printf("%d ",t);}while(t!=v);printf("\n");}return;
}
/* Your function will be put here */
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！