Number of Connected Components in an Undirected Graph

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 120 ms)

Metric	Value
Runtime	120 ms
Memory	30.5 MB
Date	2020-01-29

Solution

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();
    for (int i = 0; i < n; i++)
    {
        adjList.Add(i, new List<int>());
    }

    foreach (var edge in edges)
    {
        adjList[edge[0]].Add(edge[1]);
        adjList[edge[1]].Add(edge[0]);
    }
    bool[] visited = new bool[n];
    Queue<int> q = new Queue<int>();
    int connectedComponents = 0;
    foreach (var v in adjList.Keys)
    {
        if (!visited[v])
        {
            connectedComponents++;
            q.Enqueue(v);
            visited[v] = true;
        }
        while (q.Count != 0)
        {
            var pop = q.Dequeue();
            foreach (var e in adjList[pop])
            {
                if (!visited[e])
                {
                    q.Enqueue(e);
                    visited[e] = true;
                }
            }
        }
    }
    return connectedComponents;
    }
}

📜 1 more C# submission(s)

Submission (2020-01-29) — 136 ms, 30.7 MB

public class Solution {
    public int CountComponents(int n, int[][] edges) {
 {
    Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();
    for (int i = 0; i < n; i++)
    {
        adjList.Add(i, new List<int>());
    }
    
    foreach (var edge in edges)
    {
        adjList[edge[0]].Add(edge[1]);
        adjList[edge[1]].Add(edge[0]);
    }
    bool[] visited = new bool[n];
    int connectedComponents = 0;
    foreach (var v in adjList.Keys)
    {
        if(!visited[v])
        {
            connectedComponents++;
            dfs(v, adjList, visited);
        }           
    }
    return connectedComponents;
}}

public void dfs(int v, Dictionary<int, List<int>> adjList, bool[] visited)
{
    if(visited[v]) return;
    visited[v] = true;
    foreach (var e in adjList[v])
    {
        dfs(e, adjList, visited);
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed