求连通分量

对于一个连通性未知的图G，其极大连通分量G’就是G的连通分量。在G的连通子图中，如果包含G’的图只有G’，那么G’就是G的最大连通子图。
连通分量可以用深度优先搜索或者广度优先搜索来寻找。考虑到图可能比较稀疏，使用邻接矩阵会浪费较大的空间，这里使用邻接表来描述图的关系。

邻接表的使用方法

我们用vector来作为邻接表的容器。如果有1~n个节点，记录每个节点对应的相邻节点。如果是无向图，则在两个相邻节点中都会有对方的节点。

vector<int>G[MAXN]  //MAXN表示总节点数
void insert(int a,int b)
{
    G[a].push_back(b);
    //G[b].push_back(a); 无向图要加这一条语句  
}

邻接表表示法的优点

• 只需与边数成正比的内存空间

  邻接表表示法的缺点

• 设u的相邻顶点数量为n，那么在调查顶点u与顶点v的关系时，需要消耗O(n)来搜索邻接表。
• 难以有效删除边

求连通分量

Aizu_ALDS1_11_D
只要枚举每一个节点，把每个节点相连通的节点都标上同一个标记即可。询问的时候，查找a与b的标记是否相同，若相同，则说明他们属于同一个连通图。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int MAXN = 100000 + 10;
vector<int>node[MAXN];
int color[MAXN];


void paint(int n)   //给同一个连通图的节点上标记
{
    void dfs(int, int);
    int id = 1;
    for (int i = 0; i < n; i++)
    {
        if (color[i] == 0)
            dfs(i, id++);
    }
}

void dfs(int n, int c) //栈实现，搜索同一个连通图的所有节点
{
    stack<int>g;
    g.push(n);
    color[n] = c;
    while (!g.empty())
    {
        int v = g.top();
        g.pop();
        for (int i = 0; i < node[v].size(); i++)
        {
            if (color[node[v][i]] == 0)
            {
                color[node[v][i]] = c;
                g.push(node[v][i]);
            }
        }
    }
}
int main()
{
    int n, m, q,a,b;
    cin >> n >> m;
    while (m--)
    {
        cin >> a >> b;  //建立邻接表
        node[a].push_back(b);
        node[b].push_back(a);
    }
    paint(n);
    cin >> q;
    while (q--)
    {
        cin >> a >> b;
        if (color[a] == color[b])    cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

深搜和广搜还要加强啊。