Informasjon

Forfatter(e) François Aubry
Frist Ingen frist
Innleveringsgrense Ingen begrensning

Logg inn

Graphs - Connected components

Now that we can find all the nodes that are reachable from a given node, we are going to see how we can compute connected components of an undirected graph.

As the name suggests, the connected components of an undirected graph are the parts of the graph that are connected together, that is, the parts for which any two nodes have at least one path between them.

Example:

The following figure shows a graph on the left and its connected components on the right. Nodes on the same component are colored with the same color.

graphs-undcc/undcc.png

On the above graph, if we call BFS on node 0 we will visit nodes 0, 1, 2 and 3. In general, when we call BFS on node \(u\), it will visit the whole connected component of \(u\). Therefore we can compute all the connected components by keeping a global visited set and looping over the nodes of the graph and calling BFS for each unvisited node. Each call to BFS will visit a new connected component and we will avoid to vist the same connected component twice because the visited set will be global.

One way to represent the components is to have an array \(comp\) such that \(comp[u] = comp[v]\) if and only if nodes \(u\) and \(v\) are one the same connected component. We can achieve this by labelling all nodes of each BFS visit with an id \(compId\) that we increment every time that we start a new BFS.

The following animation illustrates this process.

graphs-undcc/anim.gif

In terms of code it consists simply of adding a loop around our BFS code to try all nodes and adding the \(comp\) array to keep track of the component of each node.

static Integer[] connectedComponents(LinkedList<Integer>[] g) {
    Integer[] comp = new Integer[g.length];
    int compId = 0;
    for(int s = 0; s < g.length; s++) {
        // check is s is already labeled
        if(comp[s] != null) continue;
        // s is not labeled, perform a BFS from it to compute its component
        // initialize the queue and visited set
        Queue<Integer> Q = new LinkedList<>();
        Q.add(s);
        // set the component of s
        comp[s] = compId;
        // loop while there are nodes in the queue to process
        while(!Q.isEmpty()) {
            int u = Q.poll();
            // we are now processing node u
            for(int v : g[u]) {
                // visit edge (u, v)
                if(comp[v] == null) {
                    // node v has not yet been visited, add it
                    Q.add(v);
                    // set the component of v
                    comp[v] = compId;
                }
            }
        }
        // finished labelling the component, increment the component id
        compId += 1;
    }
    return comp;
}

Checking the components

You will be given an undirected graph and some number of queries each of them composed by two nodes. You have to compute the number of connected components of the given graph and for each query output whether the two given nodes are on the same connected component.

Input

  • One line with two integers \(n\) and \(m\) giving the number of nodes in the graph and the number of edges respectively.
  • \(m\) lines each with two integers \(u_i\) and \(v_i\) giving that there is an undirected edge between \(u_i\) and \(v_i\). No edge will appear more than once in the input.
  • One line with one integer \(q\) giving the number of queries.
  • \(q\) lines each with two integers \(a_i\) and \(b_i\) giving the two nodes of the query.

Constraints

  • \(1 \leq n \leq 20000\)
  • \(0 \leq m \leq 100000\)
  • \(1 \leq q \leq 10000\)
  • \(0 \leq u_i, v_i < n\)
  • \(0 \leq a_i, b_i < n\)

Output

The first line must contain the number of connected components in the graph.

Then follow \(q\) lines with yes if the nodes \(a_i\) and \(b_i\) belong to the same connected component or no otherwise.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2


Maksimal filstørrelse: 1.0 MiB
Tillatte filetternavn: .java, .cpp, .py