图的连通分量寻找

连通分量

无向图G的极大连通子图称为G的连通分量（Connected Component）。任何连通图（任意两个顶点之间可达的图）都只有一个连通分量，即自身，非连通图有多个连通分量。

深度优先搜索的特点非常适合用于求解图的连通分量，每一次深度优先遍历所经过的顶点就是一个连通分量。因此只需要对图的每一个顶点调用一次深度优先遍历（注意标记访问过的顶点），就可以求得所有的连通分量。

/* 

struct UndirectedGraph
{
    size_t V, E; //V表示顶点数，E表示边数
    map<int, forward_list<int>> adj;
};

*/

void dfs(UndirectedGraph &graph, vector<int> &visited, vector<pair<int, int>> &cc, int v)
{
    visited.at(v) = 1;
    cc.push_back(v);
    for (const int &i : graph.adj.at(v))
    {
        if (visited.at(i) == 0)
        {
            cc.push_back(make_pair(v, i));
            dfs(graph, visited, i);
        }
    }
}


vector<vector<pair<int, int>>> FindConnectedComponent(UndirectedGraph &g)
{
    vector<vector<pair<int, int>>> ans;
    vector<int> visited(g.V);
    for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite)
    {
        vector<int> cc;
        for (auto &i : ite->second)
        {
            if (visited.at(i) == 0)
            {
                dfs(g, visited, cc, i);
                ans.push_back(move(cc));
            }
        }
    }
    return ans;
}

用广度优先搜索 也可以得到连通分量：

/* 

struct UndirectedGraph
{
    size_t V, E; //V表示顶点数，E表示边数
    map<int, forward_list<int>> adj;
};

*/

vector<vector<pair<int, int>>> FindConnectedComponent(UndirectedGraph &g)
{
    vector<vector<pair<int, int>>> ans;
    vector<int> visited(g.V);
    queue<int> qu;
    for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite)
    {
        vector<pair<int, int>> cc;
        if (visited.at(ite->first) == 1)
        {
            continue;
        }
        qu.clear();
        qu.push((ite->first);
        while (!qu.empty())
        {
            int tmp = qu.front();
            qu.pop();
            if (visited.at(tmp) == 1)
            {
                continue;
            }
            visited.at(tmp) = 1;
            for (const int &i : ite->second)
            {
                if (visited.at(i) == 0)
                {
                    cc.push_back(make_pair(tmp, i));
                    qu.push(i);
                }
            }
        }
        ans.push_back(move(cc));
    }
    return ans;
}