Count Connected Components in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int vis[10], g[10][10], n;
void dfs(int u) {
    vis[u] = 1;
    for (int v = 0; v < n; v++)
        if (g[u][v] && !vis[v]) dfs(v);
}
int main() {
    n = 6;
    int e[5][2] = {{0,1},{1,2},{3,4},{4,5},{0,2}};
    for (int i = 0; i < 5; i++) g[e[i][0]][e[i][1]] = g[e[i][1]][e[i][0]] = 1;
    int count = 0;
    for (int i = 0; i < n; i++)
        if (!vis[i]) { dfs(i); count++; }
    printf("Connected Components: %d", count);
}

C Output

Input:
Edges = (0–1), (1–2), (0–2), (3–4), (4–5)
Output:
Input: Graph with 6 nodes

Output:
Connected Components: 2

C++ Program

#include <iostream>
#include <vector>
using namespace std;
void dfs(int u, vector<vector<int>>& g, vector<int>& vis) {
    vis[u] = 1;
    for (int v : g[u]) if (!vis[v]) dfs(v, g, vis);
}
int main() {
    int n = 5, count = 0;
    vector<vector<int>> g(n);
    vector<pair<int,int>> edges = {{0,1},{1,2},{3,4}};
    for (auto [u, v] : edges) g[u].push_back(v), g[v].push_back(u);
    vector<int> vis(n);
    for (int i = 0; i < n; i++)
        if (!vis[i]) dfs(i, g, vis), count++;
    cout << "Connected Components: " << count;
}

C++ Output

Input:
Edges = (0–1), (1–2), (3–4)
Output:
Input: 5-node graph

Output:
Connected Components: 2

JAVA Program

import java.util.*;
class Main {
    static void dfs(int u, List<List<Integer>> g, boolean[] vis) {
        vis[u] = true;
        for (int v : g.get(u)) if (!vis[v]) dfs(v, g, vis);
    }
    public static void main(String[] args) {
        int n = 6, count = 0;
        int[][] edges = {{0,1},{1,2},{3,4}};
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) if (!vis[i]) { dfs(i, g, vis); count++; }
        System.out.println("Connected Components: " + count);
    }
}

JAVA Output

Input:
Edges = (0–1), (1–2), (3–4) on 6-node graph
Output:
Input: Adjacency list

Output:
Connected Components: 3

Python Program

g = {0:[1], 1:[0,2], 2:[1], 3:[4], 4:[3], 5:[]}
vis = set()
def dfs(u):
    vis.add(u)
    for v in g[u]:
        if v not in vis: dfs(v)
count = 0
for u in g:
    if u not in vis:
        dfs(u)
        count += 1
print("Connected Components:", count)

Python Output

Input:
Graph =
0–1, 1–2, 3–4, 5 (isolated)
Output:
Input: Dictionary adjacency list

Output:
Connected Components: 3

In-Depth Explanation

Example

Look at the Python graph:

0–1–2  and  3–4  and  5

There are three independent sets of nodes:

{0,1,2}

{3,4}

{5}

Each one of these is a connected component as there is no path from the sets.

Real-Life Analogy

Think of social media users where friendships create groups. A group of friends where each person is directly or indirectly connected is a component. If a person is not friends with anyone, they are their own component.

It's similar to defining who's in which "friend group" — folks within the same group can talk, others can't.

Why It Matters

Connected component counting is used at the core in:

Graph clustering

Network failure detection

Social network community detection

Isolated area detection in grid problems or islands

It's used to see if a system is one big blob or divided into pieces.

Learning Insights

It teaches:

How to visit components with DFS/BFS

How visited tracking is important

How a search algorithm uncovers structure in graphs

Solid foundation of graph connectivity problems

You see how easy recursion can solve a strong structural problem.

Interview & Real-World Application

You will encounter this in:

Number of provinces or islands finding

Clustering or segmentations of data

Labeling connected components in images

Identifying independent systems in networks

Typically asked in interviews as:

Island count in matrix

Number of friend circles

Component count in undirected graphs

Counting connected components in a graph is a basic graph traversal problem that aids us in identifying how many isolated groups or clusters are present in a given network. Whether you are studying social networks, planning communication systems, or cracking island counting problems in interviews, this is applicable everywhere. With effective DFS or BFS, and proper marking of visited nodes, you can find all independent parts in a graph. This tutorial offered executable code snippets in C, C++, Java, and Python, as well as conceptual observations that enable you to develop both practical and theoretical knowledge of graph connectivity.