Components & path reconstruction

Turn traversal into useful answers: count connected groups and recover the route taken.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Start a traversal at every unvisited vertex to count components in an undirected graph.
2. When discovering u from v, store parent[u] = v.
3. For a shortest unweighted route, store parents during BFS.
4. Follow parents backward from the target, then reverse the resulting list.
5. par[source]=source terminates reconstruction. A parent is assigned only once, when BFS first discovers a vertex.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: par[source]=source terminates reconstruction. A parent is assigned only once, when BFS
// first discovers a vertex.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
vector<int>shortestPath(const vector<vector<int>>&g,int s,int t){
    vector<int>par(g.size(),-1);
    queue<int>q;
    q.push(s);
    par[s]=s;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int u:g[v]){
            if(par[u]==-1){
                par[u]=v;
                q.push(u);
            }
        }
    }
    if(par[t]==-1){
        return {};
    }
    vector<int>path;
    for(int v=t;;v=par[v]){
        path.push_back(v);
        if(v==s){
            break;
        }
    }
    reverse(path.begin(),path.end());
    return path;
}
template<class T>void printValues(const vector<T>&values){
    for(int i=0;i<(int)values.size();i++){
        if(i>0){
            cout<<' ';
        }
        cout<<values[i];
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,source,target;
    cin>>n>>m>>source>>target;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<bool>seen(n+1,false);
    int components=0;
    for(int start=1;start<=n;start++){
        if(seen[start]){
            continue;
        }
        components++;
        queue<int>pending;
        pending.push(start);
        seen[start]=true;
        while(!pending.empty()){
            int vertex=pending.front();
            pending.pop();
            for(int next:graph[vertex]){
                if(!seen[next]){
                    seen[next]=true;
                    pending.push(next);
                }
            }
        }
    }
    cout<<components<<'\n';
    vector<int>path=shortestPath(graph,source,target);
    if(path.empty()){
        cout<<"UNREACHABLE\n";
    }
    else{
        printValues(path);
    }
}

Complexity analysis

O(V + E) time, O(V) auxiliary space.

Example input and output

Read n m source target, then m undirected edges (n≥1). Print the component count, then a shortest path as vertex labels, or UNREACHABLE.

Input

6 4 1 4
1 2
2 3
3 4
5 6

Output

2
1 2 3 4

There are components {1,2,3,4} and {5,6}. Following BFS parents from 4 recovers the route through 3 and 2 to 1.

Practical applications

Use components to answer connectivity queries and parent arrays to produce shortest-path witnesses.

Check your understanding

To reconstruct a route, what should you record?

Put it into practice

Count components, then find the size of the largest one.