题目
输入一个有向图,然后输入几组序列 ,判断是否是是否是拓扑序列。
这个题是英语的,网上的答案较少,所以这里我也写一个
定义
// An highlighted block
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
AdjList G;
};
typedef PtrToGNode LGraph;
题目主体
#include <stdio.h>
#include <stdlib.h>
typedef enum {false, true} bool;
#define MaxVertexNum 10 /* maximum number of vertices */
typedef int Vertex; /* vertices are numbered from 1 to MaxVertexNum */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
AdjList G;
};
typedef PtrToGNode LGraph;
LGraph ReadG(); /* details omitted */
bool IsTopSeq( LGraph Graph, Vertex Seq[] );
int main()
{
int i, j, N;
Vertex Seq[MaxVertexNum];
LGraph G = ReadG();
scanf("%d", &N);
for (i=0; i<N; i++) {
for (j=0; j<G->Nv; j++)
scanf("%d", &Seq[j]);
if ( IsTopSeq(G, Seq)==true ) printf("yes\n");
else printf("no\n");
}
return 0;
}
/* Your function will be put here */
样例和输出
Sample Input (for the graph shown in the figure):
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
Sample Output:
yes
yes
yes
no
no
我的思路非常简单(cubao):
先找到所有节点的入度,然后跟随题目给的路径跟着走,如果能走通就return 1 堵住就return 0
代码:
bool IsTopSeq( LGraph Graph, Vertex Seq[] ){
int temp[Graph->Nv];
memset(temp,0,Graph->Nv*4); //默认所有点入度为0
for(int i=0;i<Graph->Nv;i++)
{
PtrToAdjVNode p=Graph->G[i].FirstEdge; //p是从G[0]开始到G[最后]的FirstEdge的指针,也就是看每一个节点
while(p)//依次给这个节点的子入度+1
{temp[p->AdjV]++;
p=p->Next;}
}
for(int i=0;i<Graph->Nv;i++)
{
if(temp[Seq[i]-1]==0) // ==0说明能走通
{
PtrToAdjVNode p=Graph->G[Seq[i]-1].FirstEdge;
while(p)//依次给这个节点的子入度-1
{temp[p->AdjV]--;
p=p->Next;}
}
else return 0;
}
return 1; }
其实求入度那里可以优化一下的(毕竟图是固定的),没必要每次都求,不过通过了我也懒得优化啦
( ̄▽ ̄)/~~
还看到一个思路也是挺简单的,推荐一下https://blog.csdn.net/weixin_44768638/article/details/103205028