Problem Description
This is a problem of counting the number of connected components in a given graph. A connected component refers to a set of vertices that are connected to each other in the graph. For example, if A is connected to B and B is connected to C, then A, B, and C are considered one connected component. This problem can be solved using graph traversal techniques such as DFS (Depth First Search) or BFS (Breadth First Search).
Input Format
The first line contains the number of vertices N (1 ≤ N ≤ 1000) and the number of edges M (0 ≤ M ≤ 100,000).
The next M lines contain the information of each edge. Each edge is represented as a pair of two vertices.
Output Format
Output the number of connected components.
Example
Input
5 3
1 2
2 3
4 5
Output
2
In the example above, 1, 2, and 3 form one connected component, and 4 and 5 form another connected component, resulting in a total of 2 connected components.
Solution Process
To solve this problem, we will implement DFS in Swift to calculate the connected components.
1. Graph Representation
We represent the graph in the form of an adjacency list based on the input. An adjacency list is a method of storing each vertex’s connected vertices in a list. This method is memory efficient and makes traversal easier.
2. DFS Implementation
We perform the search using the DFS algorithm. We track visited vertices using a stack. If the current vertex has not been visited yet, we mark it as visited and explore all connected vertices using DFS. This marks the end of one connected component.
3. Count Connected Components
We increase the count each time we discover a new connected component whenever we visit all vertices of the graph. After visiting all the vertices, we output the final counted value.
4. Implementation in Swift
import Foundation
// Structure to represent the graph
class Graph {
var adjacencyList: [[Int]]
var visited: [Bool]
var vertexCount: Int
init(vertexCount: Int) {
self.vertexCount = vertexCount
self.adjacencyList = Array(repeating: [], count: vertexCount + 1)
self.visited = Array(repeating: false, count: vertexCount + 1)
}
func addEdge(_ u: Int, _ v: Int) {
adjacencyList[u].append(v)
adjacencyList[v].append(u) // Undirected graph
}
func dfs(_ vertex: Int) {
visited[vertex] = true // Mark current vertex as visited
for neighbor in adjacencyList[vertex] {
if !visited[neighbor] {
dfs(neighbor) // Recursive call
}
}
}
func countConnectedComponents() -> Int {
var componentCount = 0
for vertex in 1...vertexCount {
if !visited[vertex] {
dfs(vertex) // New connected component found
componentCount += 1
}
}
return componentCount
}
}
// Taking input
let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let n = firstLine[0]
let m = firstLine[1]
let graph = Graph(vertexCount: n)
for _ in 0..
Time Complexity
The time complexity of this algorithm is O(N + M). N is the number of vertices, and M is the number of edges. This is because we visit all vertices and explore all edges. This time complexity is typical for DFS or BFS algorithms.
Conclusion
The problem of counting the number of connected components can be effectively solved using graph traversal techniques like DFS or BFS. Through this problem, we have addressed the basic concepts of graphs and had the opportunity to actually implement the code using Swift. I hope that the process of implementing the algorithm has deepened your understanding of data structures and algorithms.