Question

4.1.19 Show, in the style of the figure on page 545, a detailed trace of CC for finding the connected components in the graph built by Graph’s input stream constructor for the file tinyGex2.txt (see Exercise 4.1.2).

4316631880221111 1 2682-03 10 7 7 1 2 6 5 5 3 8 4

Answer 1

It's not exactly clear what you want in the question, but I assume you want an algorithm to find the connected components in the graph. So, I will provide you with an algorithm that exactly does that plus I will provide you with a working c++ code that solves the given problem. The code will accept the input as suggested in the input section and will output all the connected components with simple numbering.

So, we can use DFS (Depth-first search)or BFS(Breadth-first search) to find out the connected components in a graph. Basically what we want to do is to isolate the vertices that are connected together. So one easy way to do this is to run a DFS or BFS on the graph and keep the DFS/BFS running as long as we can from a single source, once the BFS/DFS stops running we print all the vertices visited during that run of the DFS/BFS and then we repeat the process for the remaining unvisited vertices.

Code:-

#include <bits/stdc++.h>
#define ll long long int

using namespace std;

vector <ll> graph[100000], now;
ll vis[100000];

inline void dfs(ll x)
{
   vis[x] = true;
   now.push_back(x);
   for(auto it : graph[x])
   {
       if(!vis[it])
           dfs(it);
   }
}

int main()
{  
   ll n, m;
   cin >> n >> m;
   for(ll i = 0; i < m; i++)
   {
       ll x, y;
       cin >> x >> y;
       graph[x].push_back(y);
       graph[y].push_back(x);
   }
   ll idx = 1;
   for(ll i = 1; i <= n; i++)
   {
       if(!vis[i])
       {
           now.clear();
           dfs(i);
           for(auto it : now)
               cout << it << " ";
           cout << endl;
       }
   }
   return 0;
}
The code is kind of self-explanatory and is easy to understand. The algorithm is also fairly simple to understand and you can make changes in then dfs() function to print out the details according to your necessity. However, if you still have problems in understanding the solution then leave a comment down below and I will be more than happy to clear your doubts.