Connected Components in a Graph

This problem is an interesting one—it initially looks daunting, but upon closer inspection, it turns out to be quite approachable. The solution involves two main steps: building the graph and counting the connected components. I prefer to represent graphs using a simple Hashtable, as it makes accessing and traversing the graph straightforward and efficient. Since this problem involves an undirected graph, it's important to remember to add edges in both directions, meaning both {i, j} and {j, i} must be included.

Counting connected components is a classic graph problem that can be efficiently solved using Depth-First Search (DFS). The DFS approach systematically marks all vertices belonging to the same component, ensuring that each vertex is visited at most twice—resulting in a linear-time algorithm.

If you're curious about the detailed analysis of the algorithm, ChatGPT 4.5 provides a thorough complexity breakdown, confirming that, given the constraints, the solution is quite efficient. It's no surprise, then, that this solution beats around 90% of other submissions on LeetCode.

You can find the complete solution code below. Cheers,

ACC

public int NumberOfComponents(int[][] properties, int k)
{
    Hashtable propToNumbers = new Hashtable();

    //1. Move properties to a hash structure for quick lookup when creating the graph (in step 2)
    for (int i = 0; i < properties.Length; i++)
    {
        propToNumbers.Add(i, new HashSet());
        HashSet numbers = (HashSet)propToNumbers[i];
        for (int j = 0; j < properties[i].Length; j++)
        {
            if (!numbers.Contains(properties[i][j]))
                numbers.Add(properties[i][j]);
        }
    }

    //2. Build the graph
    Hashtable graph = new Hashtable();
    for (int i = 0; i < properties.Length; i++)
    {
        for (int j = i + 1; j < properties.Length; j++)
        {
            HashSet numbers1 = (HashSet)propToNumbers[i];
            HashSet numbers2 = (HashSet)propToNumbers[j];

            int matches = 0;
            bool isConnection = false;
            foreach (int n in numbers1)
            {
                if (numbers2.Contains(n))
                {
                    matches++;
                    if (matches >= k)
                    {
                        isConnection = true;
                        break;
                    }
                }
            }

            if (isConnection)
            {
                int[] conns = { i, j };
                for (int z = 0; z < conns.Length; z++)
                {
                    if (!graph.ContainsKey(conns[z])) graph.Add(conns[z], new Hashtable());
                    Hashtable connections = (Hashtable)graph[conns[z]];
                    if (!connections.ContainsKey(conns[(z + 1) % conns.Length])) connections.Add(conns[(z + 1) % conns.Length], new Hashtable());
                }
            }
        }
    }

    //3. Count number of connected components
    HashSet visited = new HashSet();
    int numberConnectedComponets = 0;
    for (int vertex = 0; vertex < properties.Length; vertex++)
    {
        if (!visited.Contains(vertex))
        {
            numberConnectedComponets++;
            TraverseConnectedComponent(graph, vertex, visited);
        }
    }

    return numberConnectedComponets;
}

private void TraverseConnectedComponent(Hashtable graph,
                                        int vertex,
                                        HashSet visited)
{
    if (visited.Contains(vertex)) return;
    visited.Add(vertex);

    if (graph.ContainsKey(vertex))
    {
        Hashtable connections = (Hashtable)graph[vertex];
        foreach (int node in connections.Keys)
        {
            if (!visited.Contains(node))
                TraverseConnectedComponent(graph, node, visited);
        }
    }
}