每日一题——求解连通分量个数

　

连通分量

题目描述

从键盘接收图的顶点集，关系集，创建无向图。

第一行依次输入图的顶点个数n，关系个数k，以空格隔开。顶点个数<=20

第二行依次输入顶点值，类型为字符。

接下去有k行，每行为两个字符 u 和 v，表示节点u 和 v 连通。格式为【uv】,中间不用空格间隔。

计算连通分量个数并输出。

输出一个整数，表示连通分量个数。

样例输入

6 7

ABCDEF

AB

AE

BC

CD

DA

DB

EC

样例输出

2

#include <iOStream>
using namespace std;
#define MAX_VERTEX 20

int visited[MAX_VERTEX] = { 0 };
typedef struct {
	int vertexnum;
	int arcnum;
	int arcs[MAX_VERTEX][MAX_VERTEX];
	char vertex[MAX_VERTEX];
}AdjMatrix;

void creatGragh(AdjMatrix *G)
{
	//cout << "输入图的顶点数和边数：" << endl;
	cin >> G->vertexnum >> G->arcnum;

	//cout << "输入顶点信息：" << endl;
	for (int i = 1; i <= G->vertexnum; i++)
	{
		cin >> G->vertex[i];
	}

	for (int i = 1; i <= G->vertexnum; i++)
	{//初始化邻接矩阵
		for (int j = 1; j <= G->vertexnum; j++)
		{
			G->arcs[i][j] = 0;
		}
	}

	//cout << "输入头和尾结点：" << endl;
	for (int i = 0; i < G->arcnum; i++)
	{
		int head = 0; int tail = 0;
		char chead; char ctail;
		cin >> chead >> ctail;
		for (int j = 1; j <= G->vertexnum; j++)
		{
			if (G->vertex[j] == chead)
			{
				head = j;
				for (int k = 1; k <= G->vertexnum; k++)
				{
					if (G->vertex[k] == ctail)
						tail = k;
				}
			}
		}
		G->arcs[head][tail] = 1;
		G->arcs[tail][head] = 1;
	}

}

void DFS(AdjMatrix *G, int start)
{
	//cout << G->vertex[start];
	visited[start] = 1;
	for (int i = 1; i <= G->vertexnum; i++)
	{
		if (G->arcs[start][i] == 1 && visited[i] == 0)
			DFS(G, i);
	}
}

int DFSTraverse(AdjMatrix *G)
{
	int count = 0;
	for (int i = 1; i <= G->vertexnum; i++)
		visited[i] = 0;
	for (int i = 1; i <= G->vertexnum; i++)
	{
		if (!visited[i])
		{
			DFS(G, i);
			count++;
		}
	}
	return count;
}

int main() {
	AdjMatrix *G;
	G = (AdjMatrix*)malloc(sizeof(AdjMatrix));
	creatGragh(G);
	//showGragh(G);
	cout << DFSTraverse(G) << endl;
	return 0;
}

运行结果

2

相关阅读

Gym - 101170[强连通缩点+DP]

题目链接:https://vjudge.net/problem/Gym-101170B 解题思路: 题目悄悄地告诉你，最多只含有5元环，所以我们先缩点，然后跑dp。对于一

图论 —— 图的连通性

【基本概念】 1.连通图与连通分量 1）连通图：无向图 G 中，若对任意两点，从顶点 Vi 到顶点 Vj 有路径，则称 Vi 和 Vj 是连通的，图 G 是

Telnet测试端口连通性

如何优雅的使用telnet测试端口连通性 telnet命令是TELNET协议的用户接口，它支持两种模式：命令模式和会话模式，虽然telnet支持许多

求图的连通分量

求图的连通分量 什么是连通分量 无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身

连通图 与 连通分量

这里有必要说明几个概念。 （1）在无向图中，如果顶点Vi到顶点Vj有路径，则称顶点Vi和Vj连通。 （2）如果无向图中任意两个顶点之间都连通，则称