C# Coding Test Course, Counting the Number of Connected Components

Hello! In this lecture, we will take a closer look at the algorithm problem of finding the number of connected components using C#. This problem is based on graph theory, and a connected component refers to a set of vertices that are connected to each other within the graph. Through this lecture, you will enhance your algorithmic thinking and C# programming skills to solve the problem.

Problem Description

Given a graph G, write a program to count the number of connected components in G. The graph is defined by the number of vertices N and the number of edges M, with each edge connecting two vertices.

Input Format:
- The first line will contain the number of vertices N (1 ≤ N ≤ 1000) and the number of edges M (0 ≤ M ≤ 100,000).
- The next M lines will provide the vertex numbers u and v (1 ≤ u, v ≤ N) at both ends of each edge. 

Output Format:
- Print the number of connected components on the first line.

Example

Input:
6 5
1 2
2 3
4 5

Output:
3

In this example, vertices 1, 2, and 3 form one connected component, while vertices 4 and 5 form another connected component, and vertex 6 has no connected edges, resulting in a total of 3 connected components.

Problem Solving Process

Step 1: Representing the Graph

To solve this problem, you must decide how to represent the graph. Common methods include using an adjacency list or an adjacency matrix. Using an adjacency list can reduce memory usage, making it more efficient. In C#, you can typically use Dictionary or List to implement the adjacency list.

List<int>[] graph = new List<int>[N + 1];
for (int i = 1; i <= N; i++)
    graph[i] = new List<int>();

Step 2: Input Edge Information

You need to construct the graph based on the input edge information. For each edge, you will read the two vertices and add them to each other’s list. This will complete the structure of the graph.

for (int i = 0; i < M; i++)
{
    int u = int.Parse(Console.ReadLine());
    int v = int.Parse(Console.ReadLine());
    graph[u].Add(v);
    graph[v].Add(u);
}

Step 3: Implementing DFS or BFS

To count the number of connected components, you need to explore each vertex using either DFS (Depth-First Search) or BFS (Breadth-First Search). You must manage to avoid visiting already visited vertices again. You can use a bool array to keep track of visited status.

bool[] visited = new bool[N + 1];

Next, implement the DFS method to start from the given vertex and visit all connected vertices. Each time a DFS call ends, increment the count of connected components.

void DFS(int node)
{
    visited[node] = true;
    foreach (var neighbor in graph[node])
    {
        if (!visited[neighbor])
            DFS(neighbor);
    }
}

Step 4: Implementing the Complete Algorithm

Finally, to calculate the number of connected components, iterate through all vertices, calling DFS for unvisited vertices and count each connected component. Print the final count of connected components.

int count = 0;

for (int i = 1; i <= N; i++)
{
    if (!visited[i])
    {
        DFS(i);
        count++;
    }
}

Console.WriteLine(count);

Complete Code

The entire code written in C# based on the above steps is as follows:

using System;
using System.Collections.Generic;

class Program
{
    static List<int>[] graph;
    static bool[] visited;
    static int N, M;

    static void Main()
    {
        var input = Console.ReadLine().Split();
        N = int.Parse(input[0]);
        M = int.Parse(input[1]);

        graph = new List<int>[N + 1];
        for (int i = 1; i <= N; i++)
            graph[i] = new List<int>();

        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split();
            int u = int.Parse(input[0]);
            int v = int.Parse(input[1]);
            graph[u].Add(v);
            graph[v].Add(u);
        }

        visited = new bool[N + 1];
        int count = 0;

        for (int i = 1; i <= N; i++)
        {
            if (!visited[i])
            {
                DFS(i);
                count++;
            }
        }

        Console.WriteLine(count);
    }

    static void DFS(int node)
    {
        visited[node] = true;
        foreach (var neighbor in graph[node])
        {
            if (!visited[neighbor])
                DFS(neighbor);
        }
    }
}

Conclusion

In this lecture, we solved the problem of counting the number of connected components in a graph using the C# language. By utilizing basic DFS/BFS techniques from graph theory, we enhanced our algorithmic thinking process while exploring and seeking solutions to the problem. I hope you continue to practice by solving similar problems to improve your skills!

Thank you!