PTA Count Connected Components 分数 10 作者 陈越 单位 浙江大学
2023-12-14 00:58:54
Write a function to count the number of connected components in a given graph.
Format of functions:
int CountConnectedComponents( LGraph Graph );
where LGraph is defined as the following:
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;
The function CountConnectedComponents is supposed to return the number of connected components in the undirected Graph.
Sample program of judge:
#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 0 to MaxVertexNum-1 */
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 */
int CountConnectedComponents( LGraph Graph );
int main()
{
LGraph G = ReadG();
printf("%d\n", CountConnectedComponents(G));
return 0;
}
/* Your function will be put here */
Sample Input (for the graph shown in the figure):
8 6
0 7
0 1
2 0
4 1
2 4
3 5
Sample Output:
3
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
answer:
void DFS(LGraph Graph, Vertex V, bool visited[])
{
visited[V] = true;
PtrToAdjVNode p = Graph->G[V].FirstEdge;
while (p)
{
if (!visited[p->AdjV])DFS(Graph, p->AdjV, visited);
p = p->Next;
}
}
int CountConnectedComponents(LGraph Graph)
{
Vertex V;
bool visited[MaxVertexNum];
int Components = 0;
for (V = 0; V < Graph->Nv; V++)
{
visited[V] = false;
}
for (V = 0; V < Graph->Nv; V++)
{
if (!visited[V])
{
DFS(Graph, V, visited);
Components++;
}
}
return Components;
}
本题是求一个图的联通分支个数。
文章来源:https://blog.csdn.net/m0_73804746/article/details/134819998
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!