Sample code in c ++ / java? What is meant is the search for connected components using depth / width traversal. I'm going to look for the adjacency matrix.

  • one
    Ask the question: where are you going to search and an example of what code is the search code? - IAZ

2 answers 2

As far as I understand, the author of the problem needs an algorithm for searching for components of a constraint, not a component of strong connectivity, and this is not at all the same thing!

  int n, a [100] [100], cur = 0;
     fin >> n;
     for (int i = 0; i <n; i ++)
         for (int j = 0; j <n; j ++)
             fin >> a [i] [j];
     vector <int> was (n, -1);
     queue <int> q;
     for (int i = 0; i <n; i ++)
     {
         if (was [i]! = -1)
            continue;
         q.push (i);
         while (! q.empty ())
         {
               int v = q.front ();
               q.pop ();
               if (was [v]! = -1)
                  continue;
               was [v] = cur;
               for (int j = 0; j <n; j ++)
                   if (a [i] [j]! = 0 && was [j] == -1)
                      q.push (j);
         }
         cur ++;
     }
This code reads the graph specified by the adjacency matrix (but I advise you to use adjacency lists). As a result, the vector was for each vertex will contain the number of its connected components, and cur - the number of connected components.

  • In the first version of the message it was asked about the components of strong connectivity. Who knows, maybe soon the question will evolve into the problem of graph isomorphism. - yapycoder
  • In addition, if you go to the library website, you can easily find other algorithms. For example, boost.org/doc/libs/1_46_1/libs/graph/doc/… - yapycoder

In Boost there is a library for working with graphs, here are the components of connectivity: strong_components .

It’s strongly recommended that you compile the algorithm using DFS.