求解连通图问题的常用方法

判断图是否连通以及连通子图个数的问题

一般常见的解法是 并查集或者图的遍历（dfs/bfs）

连通图

经典并查集写法

#include <bits/stdc++.h>
using namespace std;
const int N = 1010,M = 5050;
int p[N];
int find(int x)
{
    if (p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    while (cin>>n>>m)
    {
        for (int i=1;i<=n;i++) p[i]=i;
        while (m--)
        {
            int a,b;
            cin>>a>>b;
            int pa = find(a),pb = find(b);
            if (pa!=pb)
                p[pa]=pb;
        }
        
        bool flag = false;
        int ans = find(1);
        for (int i=2;i<=n;i++)
        {
            if (find(i)!=ans)
            {
                flag = true;
                break;
            }
        }
        if (flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

dfs遍历

#include <bits/stdc++.h>
using namespace std;
const int N = 1010,M = N*N;
int h[N],e[M],ne[M],idx;
bool st[N];
int n,m;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    st[u] = true;
    for (int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if (!st[j])
            dfs(j);
    }
}
int main()
{
    while (cin>>n>>m)
    {
        memset(h,-1,sizeof h);
        memset(st,0,sizeof st);
        while (m--)
        {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }
        dfs(1);
        bool flag = false;
        for (int i=1;i<=n;i++)
        {
            if (!st[i])
            {
                flag = true;
                break;
            }
        }
        if (flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

bfs遍历

#include <bits/stdc++.h>
using namespace std;
const int N = 1010,M = N*N;
int h[N],e[M],ne[M],idx;
int n,m;
bool st[N];

void add(int a,int b)
{
    e[idx] =b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int u)
{
    queue<int>q;
    st[u] = true;
    q.push(u);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = true;
                q.push(j);
            }
        }
    }
}
int main()
{
    while (cin>>n>>m)
    {
        memset(h,-1,sizeof h);
        memset(st,0,sizeof st);
        while (m--)
        {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }
        
        bfs(1);
        bool flag = false;
        for (int i=1;i<=n;i++)
        {
            if (!st[i])
            {
                flag = true;
                break;
            }
        }
        if (flag) puts("NO");
        else puts("YES");
    }
    return 0;
}