首页 > 代码库 > 连通分量个数

连通分量个数


在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,

否则,称该图为非连通图,则其中的极大连通子图称为连通分量,这里所谓的极大是指子图中包含的顶点个数极大。
例如:一个无向图有5个顶点,1-3-5是连通的,2是连通的,4是连通的,则这个无向图有3个连通分量。
求连通分量的个数


当然也可以用并查集

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
const int N = 210;
const int maxn = 2000;
const int maxm = 201010;
const int inf = 1e8;
#define MIN INT_MIN
#define MAX 1e6
#define LL long long
#define init(a) memset(a,0,sizeof(a))
#define FOR(i,a,b) for(int i = a;i<b;i++)
#define max(a,b) (a>b)?(a):(b)
#define min(a,b) (a>b)?(b):(a)
using namespace std;
int ma[50][50];
bool vis[50];
int num = 0,n;

void DFS(int k)
{
    vis[k] = 1;
    FOR(i,1,n+1)
    {
        if(ma[k][i] && !vis[i])
        {
            DFS(i);
        }
    }
}
int main()
{
    int t,m,a,b;
    scanf("%d",&t);
    while(t-- && scanf("%d%d",&n,&m))
    {
        init(ma);init(vis);
        num = 0;
        FOR(i,0,m)
        {
            scanf("%d%d",&a,&b);
            ma[a][b] = ma[b][a] = 1;
        }
        FOR(i,1,n+1)
        {
            if(!vis[i])
            {
            DFS(i);
            num++;
            }

        }
        cout<<num<<endl;
    }
    return 0;
}


连通分量个数