Day 33 | Connected Components | C++

I know we studied DFS, BFS, and also the shortest path using BFS. You might be feeling that we are moving too fast, but graphs are generally based on multiple basic concepts used simultaneously.

Have you noticed that there is no "DFS" problem category in Codeforces but "DFS-and-similar"? DFS is simply like running a loop on an array equivalent to a graph. You need to do some other calculations using traversals.

Like you have other logical units in an array like sub-array, subsets, sorted order, etc we also have different units in graphs like Connected Components, Bridges, Topological Sort, etc. which helps us in solving multiple problems.

Let's try to understand what are Connected Components in an undirected Graph.

Technical Definition -

The connected component of an undirected graph is a set of vertices where there will a path will be available between two any two vertices in the set

Let's understand it with an example

Considering the graph given above, it is evident that there are two connected components -

1. { 1, 2, 3, 4 } Take any two nodes in this set and you will notice that there is a path between them.

2. { 5, 6, 7 } Take any two nodes in this set and you will notice that there is a path between them.

If you take a node from set 1 and another node from set 2, then there is no path between them.

That is the concept of Connected Components, that's it.

How to know if two nodes belong to same connected component or not?

There is one very cool observation here-

• If you start a DFS (or BFS) from any node in set 1, then it will visit all the nodes in set 1. But it will not be able to visit any node in set 2.

So if you start a DFS (or BFS) from any node, then you can mark it as a number for the component.

Let's try this with the graph above -

The graph above is -

Line 1 - vertices and edges count
Line 2 to edges + 1 - two integers denoting edge
7 6
1 2
2 3
2 4
4 3
5 6
5 7

Code

#include<bits/stdc++.h>
using namespace std;

void dfs(int u, vector<vector<int>>& g, vector<int>& vis, vector<int>& component){
    if(vis[u])return;
    vis[u] = 1;
    component.push_back(u);
    for(int v: g[u]){
        dfs(v, g, vis, component);
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<vector<int>> connected_components;
    vector<int> vis(n+1, 0);
    for(int i = 1; i <= n; i++){
        // Not yet visited
        if(vis[i] == 0){
            // new component
            connected_components.push_back(vector<int>());
            dfs(i, g, vis, connected_components.back());
        } 
    }
    //Print Components;
    for(int i = 0; i < connected_components.size(); i++){
        vector<int>& component = connected_components[i];
        for(int i : component)cout << i << " ";
        cout << "\n";
    }
}

Output

1 2 3 4 
5 6 7 

Let's solve Bear and Friendship Condition

Note - [2 codes provided - easier to understand the process (code 1), easier to write code (code 2)]

This is a fun problem. I know I call every problem fun but believe me that every problem is actually fun.

Notice that if A is a friend with B and B is a friend with C then A should also be friends with C.

Hence there should be a direct edge between all the pairs of people in one connected component as people in one connected component are directly or indirectly friends.

Learning Moment

A set of vertices (can be a full graph or one connected component) in which every pair of vertices have an edge between them is called Fully Connected.

If we are talking about a graph then we called it a fully connected graph, if it's a component then a fully connected component and stuff. In a fully connected set of N vertices, Node 1 will be connected to (2, 3, 4, ..., N) nodes using N-1 edges Node 2 will be connected to (3, 4, 5, ..., N) nodes using N-2 edges (1-2 already included above) Node 3 will be connected to (4, 5, 6 ..., N) nodes using N-3 edges (1-3, 2-3 already included above) ... Node N-1 will be connected to only Nth nodes using 1 edge Node N will be connected to no nodes using 0 edges

Hence total number of edges = 1+2+3+...+(N-2)+(N-1) = N * (N-1) / 2

Hence, we can just find the size of each connected component and check if it is fully connected or not.

When we are done with finding connected_components using the code above,

Then we

1. Map which node belongs to which component

    map<int,int> component_node_is_in;
    /*
    * Now we will fill component_node_is_in
    */
    for(int i = 0; i < connected_components.size(); i++){
        for(int j : connected_components[i])
            component_node_is_in[j] = i;
    }

2. Count edges for each component using 1

    map<int,int> edge_count_for_component;
    /*
    * For all edges, we see in which component they are in
    */
    for(auto i: edges){
        // use either i.first or i.second as both are in same component
        int component = component_node_is_in[i.first];
        edge_count_for_component[component]++;
    }

3. Check all the components are fully connected

/*
* Checking all components if they fully components or not
*/
for(int i = 0; i < connected_components.size(); i++){
    int edge_count = edge_count_for_component[i];
    int node_count = connected_components[i].size();
    long long full_connected_edges = (node_count*1LL*(node_count - 1)/2);
    if(edge_count != full_connected_edges){
        cout << "NO\n";
        return 0;
    }
}

You can find the complete submission here - Submission Link

Note - If you count the number of nodes in each component, count the required edges for fully connected components for this number of nodes. Then the sum of edges in fully connected components should be equal to M if all are fully connected.

Hence you can simply code it like this

#include<bits/stdc++.h>
using namespace std;

int dfs(int u, vector<vector<int>>& g, vector<int>& vis){
    if(vis[u])return 0;
    vis[u] = 1;
    int cnt = 1;
    for(int v: g[u]){
        cnt+=dfs(v, g, vis);
    }
    return cnt;
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> vis(n+1, 0);
    long long req = 0;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            int nodes = dfs(i, g, vis);
            req += (nodes * 1LL * (nodes - 1) / 2);
        }
    }
    if(req == m)cout << "YES\n";
    else cout << "NO\n";
}