图的基本概念-连通分支数

图的基本概念-连通分支数

在这里插入代码片
// 图的邻接表存储结构，C++ 简化版

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1000000;
vector<vector<int>> g;
int ans=0;
//vector <int>g[maxn];
int nv;
int ne;
bool vis[maxn];
bool Hash[maxn];
void DFS(int nv){//u为当前访问的顶点标号，depth为深度
	vis[nv]=true;//设置u已被访问
	if(g[nv].size()==0)
        ans++;
	for(int i=0;i<g[nv].size();++i){//对从u出发可以到达的所有顶点v
		int v=g[nv][i];
		if(!vis[v])
            DFS(v);//如果v未被访问，访问v，深度+1
	}
}
int DFSTrave(){//遍历该图

	for(int u=0; u<=nv; ++u){//对每个顶点u
		if(Hash[u] && !vis[u]){//如果u未被访问
			DFS(u);//访问u和u所在的连通块
			++ans;//连通块数+1
		}
	}
	return ans;
	//printf("%d\n",ans);
}
int main(void)
{
    // 输入顶点个数 nv 和边的个数 ne
    cin >> nv >> ne;
    g.resize(nv); // 根据顶点个数分配空间
    // 输入边
    for (int e = 0; e < ne; e++) {
        int u, v;
        cin >> u >> v; // 读取一条边 (u,v)
        g[u].push_back(v); // u --> v
        g[v].push_back(u); // 无向图增加 v --> u
        Hash[v]=Hash[u]=true;
    }
    DFSTrave();
    for(int i=0;i<nv;i++)//如果有孤立的点存在的话也算一个连通分量
    {
        if(g[i].size()==0)
            ans++;
    }
	printf("%d\n",ans);
    return 0;
}

更新，又微改了一下

```cpp

```cpp
// 图的邻接表存储结构，C++ 简化版
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1000000;
vector<vector<int>> g;
int ans=0;
int nv;
int ne;
bool vis[maxn];
bool Hash[maxn];
void DFS(int nv){//u为当前访问的顶点标号，depth为深度
	vis[nv]=true;//设置u已被访问
	for(int i=0;i<g[nv].size();++i){//对从u出发可以到达的所有顶点v
		int v=g[nv][i];
		if(!vis[v])
            DFS(v);//如果v未被访问，访问v，深度+1
	}
}
int DFSTrave(){//遍历该图
	for(int u=0; u<=nv; ++u){//对每个顶点u
		if(Hash[u] && !vis[u]){//如果u未被访问并且u存在。
			DFS(u);//访问u和u所在的连通块
			++ans;//连通块数+1
		}
	}
	return ans;
}

int main(void)
{
    // 输入顶点个数 nv 和边的个数 ne
    cin >> nv >> ne;
    g.resize(nv); // 根据顶点个数分配空间
    // 输入边
    for (int e = 0; e < ne; e++) {
        int u, v;
        cin >> u >> v; // 读取一条边 (u,v)
        g[u].push_back(v); // u --> v
        g[v].push_back(u); // 无向图增加 v --> u
        Hash[u]=Hash[v]=true;//u可能并不是连续的，所以在dfsTrave的时候要辨别一下，有没有这个顶点
    }
    DFSTrave();
    for(int i=0;i<nv;i++)
    {
        if(g[i].size()==0)
            ans++;
    }
	printf("%d\n",ans);
    return 0;
}