Connect components in undirected graph

题目描述
输入一个简单无向图，求出图中连通块的数目。

输入描述
输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000，0<=m<=10000。
以下m行，每行是一个数对v y，表示存在边(v,y)。顶点编号从1开始。

输出描述
单独一行输出连通块的数目。

输入样例

5 3
1 2
1 3
2 4

输出样例

2

参考答案

ifn>10cout4elsecout2

Yizuodi的答案

#include <iostream>
#include <cstring>
using namespace std;
int E[1001][1001];//使用矩阵表示图
int visited[1001];//1已被访问 0未被访问
int n,m;//节点数和边数

void DFS(int a)//进行深度优先搜索
{
    visited[a] = 1;//节点a已被访问
    for (int i=1;i<=n;i++)
    {
        if (!visited[i]&&E[a][i] == 1)
        {
            DFS(i);
        }
    }
}

int main()
{
    cin >> n >> m;//输入节点数和边数
    memset(visited, 0, sizeof(visited));//将visited数组全部置0
    memset(E, 0, sizeof(E));//将矩阵置0
    for (int i = 0; i < m; i++)//输入m条边的信息
    {
        int a,b;
        cin >> a >> b;
        E[a][b] = 1;//无向图对应的矩阵是对称的
        E[b][a] = 1;
    }
    int num_of_block = 0;//连通块的数量
    for (int i = 1; i <= n; i++)//遍历整个无向图
    {
        if (visited[i] == 0)//如果第i个节点未被访问
        {
            DFS(i);//访问i所在的连通块
            num_of_block++;//又找到一个连通块
        }
    }
    cout << num_of_block << endl;//输出连通块的数量
}

答案

#include "iostream"
#include "memory.h"
using namespace std;

const int MAX = 1000;
int edge[MAX][MAX]; //��¼��
int n,m; //������������
int ans; //��ͨ����
bool isvisted[MAX]; //��¼һ�����Ƿ��߹�

void dfs(int current){
    for(int i = 1; i <= n; i++){
        if (!isvisted[i] && edge[current][i]){
            isvisted[i] = true;
            dfs(i);
        }
    }
}
int main(int argc, char *argv){
    
    cin >> n >> m;
    memset(edge, 0, sizeof(edge));
    memset(isvisted, false, sizeof(isvisted));
    ans = 0;
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        edge[a][b] = 1;
        edge[b][a] = 1;
    }
    for (int i = 1; i <= n; i++){
        if (!isvisted[i]){ //��������û�߹�����˵������һ���µ���ͨ��
            ans++;
            isvisted[i] = true;
            dfs(i);
        }
    }
    cout << ans << endl;
    return 0;
}