Count Unreachable Pairs of Nodes in an Undirected Graph - Problem

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.

Two nodes are unreachable from each other if there is no path connecting them in the graph.

Input & Output

Example 1 — Basic Connected Components

$ Input: n = 3, edges = [[0,1],[0,2],[1,2]]

› Output: 0

💡 Note: All nodes are connected through edges. Node 0 connects to 1 and 2, creating one big component of size 3. Since all nodes can reach each other, there are 0 unreachable pairs.

Example 2 — Multiple Components

$ Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]

› Output: 14

💡 Note: Component 1: {0,2,4,5} (size 4), Component 2: {1,6} (size 2), Component 3: {3} (size 1). Unreachable pairs: 4×3 + 2×1 = 12 + 2 = 14.

Example 3 — No Edges

$ Input: n = 3, edges = []

› Output: 3

💡 Note: No edges means each node is its own component. Pairs: (0,1), (0,2), (1,2) = 3 unreachable pairs total.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ edges.length ≤ 2 × 10⁵
edges[i].length == 2
0 ≤ ai, bi < n
ai ≠ bi
There are no repeated edges

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is that nodes in different connected components can never reach each other. Find all connected components using DFS or BFS, then calculate unreachable pairs by multiplying sizes of different components. Best approach is DFS/BFS Connected Components with Time: O(n + m), Space: O(n + m).

Common Approaches

✓ BFS Connected Components

⏱️ Time: O(n + m) Space: O(n + m)

Similar to DFS approach but uses BFS (breadth-first search) to traverse the graph. BFS explores nodes level by level using a queue, which can be more intuitive for some developers and avoids recursion stack issues.

Brute Force - Check All Pairs

⏱️ Time: O(n³) Space: O(n)

Try every possible pair of nodes and use BFS/DFS to determine if they're connected. This approach directly answers the question but is very inefficient.

DFS Connected Components

⏱️ Time: O(n + m) Space: O(n + m)

Use DFS to identify connected components. Nodes in the same component can reach each other, but nodes in different components cannot. Calculate unreachable pairs by multiplying sizes of different components.

BFS Connected Components — Algorithm Steps

Build adjacency list from edges
Use BFS to find all connected components
Calculate unreachable pairs from component sizes
Return total count

Visualization

Tap to expand

Step-by-Step Walkthrough

Queue Start

Add starting node to queue

Explore Level

Process all neighbors level by level

Count Components

Calculate pairs between components

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int* data;
    int front, rear, capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->capacity = capacity;
    q->data = (int*)malloc(capacity * sizeof(int));
    q->front = q->rear = 0;
    return q;
}

void enqueue(Queue* q, int val) {
    q->data[q->rear++] = val;
}

int dequeue(Queue* q) {
    return q->data[q->front++];
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

void freeQueue(Queue* q) {
    free(q->data);
    free(q);
}

int bfs(int** graph, int* graphSize, int start, bool* visited, int n) {
    Queue* queue = createQueue(n);
    enqueue(queue, start);
    visited[start] = true;
    int size = 0;
    
    while (!isEmpty(queue)) {
        int node = dequeue(queue);
        size++;
        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                enqueue(queue, neighbor);
            }
        }
    }
    
    freeQueue(queue);
    return size;
}

long long solution(int n, int** edges, int edgesSize) {
    int** graph = (int**)malloc(n * sizeof(int*));
    int* graphSize = (int*)calloc(n, sizeof(int));
    bool* visited = (bool*)calloc(n, sizeof(bool));
    
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0], b = edges[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    int componentSizes[n];
    int numComponents = 0;
    
    // Find all connected components using BFS
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int componentSize = bfs(graph, graphSize, i, visited, n);
            componentSizes[numComponents++] = componentSize;
        }
    }
    
    // Calculate unreachable pairs
    long long totalPairs = 0;
    long long remainingNodes = n;
    
    for (int i = 0; i < numComponents; i++) {
        remainingNodes -= componentSizes[i];
        totalPairs += (long long)componentSizes[i] * remainingNodes;
    }
    
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSize);
    free(visited);
    
    return totalPairs;
}

int parseEdges(char* line, int*** edges) {
    if (strcmp(line, "[]") == 0) {
        *edges = NULL;
        return 0;
    }
    
    int maxEdges = 1000;
    *edges = (int**)malloc(maxEdges * sizeof(int*));
    for (int i = 0; i < maxEdges; i++) {
        (*edges)[i] = (int*)malloc(2 * sizeof(int));
    }
    
    int edgeCount = 0;
    char* ptr = line;
    
    while (*ptr) {
        if (*ptr == '[') {
            ptr++;
            int a = 0, b = 0;
            // Parse first number
            while (*ptr >= '0' && *ptr <= '9') {
                a = a * 10 + (*ptr - '0');
                ptr++;
            }
            // Skip comma
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
            if (*ptr == ',') ptr++;
            // Parse second number
            while (*ptr >= '0' && *ptr <= '9') {
                b = b * 10 + (*ptr - '0');
                ptr++;
            }
            
            (*edges)[edgeCount][0] = a;
            (*edges)[edgeCount][1] = b;
            edgeCount++;
        }
        ptr++;
    }
    
    return edgeCount;
}

int main() {
    int n;
    scanf("%d", &n);
    getchar(); // consume newline
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    // Remove trailing newline
    line[strcspn(line, "\n")] = 0;
    
    int** edges;
    int edgesSize = parseEdges(line, &edges);
    
    printf("%lld\n", solution(n, edges, edgesSize));
    
    if (edges) {
        for (int i = 0; i < 1000; i++) {
            free(edges[i]);
        }
        free(edges);
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Visit each node once and each edge once during BFS traversal

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency list plus BFS queue storage

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Count Unreachable Pairs of Nodes in an Undirected Graph - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Connected Components — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler