我的答案 输出是 0 0 32765
No Cycle
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define INFINITY 65535
typedef struct EdgeNode{ // 边表结点
int adjvex; // 邻接点域,存储该顶点对应的下标
int weight; // 用于存储权值,对于非网图可以不需要
struct EdgeNode *next; // 链域,指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{ // 顶点表结点
int inDegree; // 顶点入度
int data; // 顶点域,存储顶点信息
EdgeNode *firstEdge; // 边表头指针
}VertexNode;
typedef struct Graph{
int numNodes, numEdges;
VertexNode AdjList[MAXVEX];
}GraphAdjList;
void CreateALGraph(Graph &G){
int i , j , k ;
for(i = 0; i < G.numNodes; i++){
G.AdjList[i].firstEdge = NULL; // 初始化边表的头指针为空
G.AdjList[i].inDegree = 0; // 初始化顶点的入度为0
}
for(k = 0; k < G.numEdges; k++){ // 因为是有向图,所以对于每条有向边来说只需插入一个新的表结点(假设采用头插入法)
scanf("%d%d", &i, &j) ;
EdgeNode *p = (EdgeNode *)malloc(sizeof(EdgeNode));
p->adjvex = j ;
p->next = G.AdjList[i].firstEdge;
G.AdjList[i].firstEdge = p;
G.AdjList[j].inDegree ++; // 编号为j的顶点入度增加1
}
}
// 拓扑排序,若GL无回路输出拓扑排序序列并返回1,否则返回0。
int TopologicalSort(GraphAdjList G){
//
}
int main(void){
GraphAdjList G;
scanf("%d %d",&G.numNodes,&G.numEdges);
CreateALGraph(G);
int result = TopologicalSort(G);
if (result==1) printf("No Cycle\n");else printf("Cycle\n");
return 0;
}
输入
第1行输入两个整数,分别表示图中的顶点数n和边数m
第2-m+1行每行输入两个整数i和j,表示编号为i的顶点和编号为j的顶点之间有一条边(顶点编号从0开始)
输出
第1行输出一个拓扑序列,每两个顶点编号之间用空格隔开。
第2行输出一个字符串No Cycle(如果原有向图中没有环)或者Cycle(如果原有向图有环)
样例输入 Copy
3 3
0 1
0 2
1 2
样例输出 Copy
0 1 2
No Cycle
我的答案
int TopologicalSort(GraphAdjList G){
EdgeNode* e;
int i, k, gettop;
int top = 0;
int count = 0;
int* stack;
stack = (int*)malloc(G.numNodes * sizeof(int));
for (i = 0;i<G.numNodes; i++)
if (G.AdjList[i].inDegree == 0)
stack[++top] = i;
while (top != 0)
{
gettop = stack[top--];
printf("%d ", G.AdjList[gettop].data);
count++;
for (e = G.AdjList[gettop].firstEdge; e; e = e->next)
{
k = e->adjvex;
if (!(--G.AdjList[k].inDegree))
stack[++top] = k;
}
}
printf("\n");
if (count < G.numNodes)
return 0;
else
return 1;
}