Gears algorithm (graphs)

hexes are numbered from 0 to N (N <= 10). A pair of junction pairs in the form of C [i, j] = 1 is specified if the gear with number i is in gear with the gear j, where 1 <= i

Decision

We denote clockwise rotation by zero, against one. We first assign the gear with the given number number zero. In the next step, the numbers 1 will be assigned to all gears linked to a given gear (they will rotate in the opposite gear 1 side). Then we assign the values ​​0 and so on to all gears that are meshed with the ones numbered in the previous step.

We will repeat the process until either a new gear is assigned a new value at the next step, and then the gear with the given number can be turned, and the number of gears considered is the desired number of gears, or at some step the gear mark changes from 1 to 0 or from 0 to 1, and then the system will not start moving.

The value of the direction of rotation of the gear will be stored in the array rotate. To bypass the gears and assign values ​​to the array rotate, we will use a wide search.

Formal description

  Gears ()
 1. Create an adjacency matrix for the graph.
 2. Read the number of the starting gear.
 3. Make a search in width from the starting vertex (pp.3.1-3.5):
    3.1.  Initialize the values ​​of the array of directions to -1.
    3.2.  Set the direction of rotation of the starting vertex zero.
    3.3.  Add a start point to the queue.
    3.4.  While the queue is not empty and the gear rotation has not been replaced,
         repeat paragraphs  3.4.1-3.4.5:
         3.4.1.  Get the current top from the queue.
         3.4.2.  Find all the instance vertices.
         3.4.3.  If no direction was found for the vertex found
                rotation, then set the rotation to a different direction
                the previous gear and add the top to the queue.
         3.4.4.  If the vertex found has the same direction of rotation,
                like the previous one, then assume that the rotation has occurred
                gears.
         3.4.5.  Remove top from queue.
 4. If the replacement did not happen, then assume that the gear system will be 
    rotate and find the number of rotating gears; 
    otherwise, assume that the system will not rotate.   

An example of a graph of two connected components for the "Gears" problem.

If you start any gear from the first component (No. 0 to No. 6), then the system will rotate, and the gears with the same direction of rotation are indicated in the same color. If you run any gear from the second connectivity component (No. 7 to No. 11), then the system will not rotate, as the gears 8 and 9 will have the same direction of rotation.