无向图的连通分支---DFS

java

Description
输入一个无向图G，计算G的连通分支数。=
Input
有多个无向图数据。每个无向描述的第1行是两个整数n和e，分别表示顶点数和边数。接着有e行，每行有2个整数a、b，分别是一条边的两个端点（起点和终点）。两个图之间空一行。
Output
对每个无向图，输出图中连通分支个数。
Sample Input
2 1
1 2

5 8
1 2
1 3
1 4
1 5
2 3
2 4
3 4
4 5
Sample Output
1
1

java版本：

import java.util.*;
public class Main {
    public static boolean [] vis = new boolean[1000];
    public  static  ArrayList<Integer> [] list= new ArrayList[1000];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int e = scanner.nextInt();
            for(int i=0; i<1000;i++){
                vis[i] = false;
                list[i] = new ArrayList<>();
            }
            for(int i=0; i<e; i++){
                int st = scanner.nextInt();
                int ed = scanner.nextInt();
                st--;ed--;
                list[st].add(ed);
                list[ed].add(st);
            }
            int count = 0;
            for(int i=0;i<n;i++){
                if(vis[i] == false) {
                    dfs(i);
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    public static void dfs(int i){
        for(int ele = 0; ele<list[i].size(); ele++){
            if(vis[list[i].get(ele)] == false){
                vis[list[i].get(ele)] = true;
                dfs(list[i].get(ele));
            }
        }
    }
}

C++版本：

#include<iostream>
#include<math.h>
#include<vector>
#include<memory.h>
using namespace std;
#define N 1000
vector<int> G[N];
bool vis[N];
void dfs(int i){
    for(const int &j : G[i]){
        if(!vis[j]){
            vis[j] = true;
            dfs(j);
        }
    }
}
int main(){
    int n,e;
    while(cin >> n >> e){
        memset(vis,0,sizeof(vis));
        for(int i=0; i<N;i++)
            G[i].clear();
        while(e--){
            int st,ed;
            cin >> st >> ed;
            st--;
            ed--;
            G[st].push_back(ed);
            G[ed].push_back(st);
        }
        int count = 0;
        for(int i=0; i<n; i++){
            if(!vis[i]){
                dfs(i);
                count++;
            }
        }
        cout << count << endl;
    }
}