Problem Description<\/h2>\n
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).<\/p>\n
Input Format<\/h3>\n\n The first line contains the number of vertices N (1 \u2264 N \u2264 1000) and the number of edges M (0 \u2264 M \u2264 100,000).\n The next M lines contain the information of each edge. Each edge is represented as a pair of two vertices.\n <\/pre>\nOutput Format<\/h3>\n\n Output the number of connected components.\n <\/pre>\n<\/section>\n\nExample<\/h2>\nInput<\/h3>\n\n 5 3\n 1 2\n 2 3\n 4 5\n <\/pre>\nOutput<\/h3>\n\n 2\n <\/pre>\nIn 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.<\/p>\n<\/section>\n\nSolution Process<\/h2>\n
To solve this problem, we will implement DFS in Swift to calculate the connected components.<\/p>\n
1. Graph Representation<\/h3>\n
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.<\/p>\n
2. DFS Implementation<\/h3>\n
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.<\/p>\n
3. Count Connected Components<\/h3>\n
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.<\/p>\n
4. Implementation in Swift<\/h3>\n\n import Foundation\n\n \/\/ Structure to represent the graph\n class Graph {\n var adjacencyList: [[Int]]\n var visited: [Bool]\n var vertexCount: Int\n\n init(vertexCount: Int) {\n self.vertexCount = vertexCount\n self.adjacencyList = Array(repeating: [], count: vertexCount + 1)\n self.visited = Array(repeating: false, count: vertexCount + 1)\n }\n\n func addEdge(_ u: Int, _ v: Int) {\n adjacencyList[u].append(v)\n adjacencyList[v].append(u) \/\/ Undirected graph\n }\n\n func dfs(_ vertex: Int) {\n visited[vertex] = true \/\/ Mark current vertex as visited\n for neighbor in adjacencyList[vertex] {\n if !visited[neighbor] {\n dfs(neighbor) \/\/ Recursive call\n }\n }\n }\n\n func countConnectedComponents() -> Int {\n var componentCount = 0\n for vertex in 1...vertexCount {\n if !visited[vertex] {\n dfs(vertex) \/\/ New connected component found\n componentCount += 1\n }\n }\n return componentCount\n }\n }\n\n \/\/ Taking input\n let firstLine = readLine()!.split(separator: \" \").map { Int($0)! }\n let n = firstLine[0]\n let m = firstLine[1]\n let graph = Graph(vertexCount: n)\n\n for _ in 0..\n<\/section>\n\nTime Complexity<\/h2>\n
Output Format<\/h3>\n\n Output the number of connected components.\n <\/pre>\n<\/section>\n\nExample<\/h2>\nInput<\/h3>\n\n 5 3\n 1 2\n 2 3\n 4 5\n <\/pre>\nOutput<\/h3>\n\n 2\n <\/pre>\nIn 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.<\/p>\n<\/section>\n\nSolution Process<\/h2>\n
To solve this problem, we will implement DFS in Swift to calculate the connected components.<\/p>\n
1. Graph Representation<\/h3>\n
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.<\/p>\n
2. DFS Implementation<\/h3>\n
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.<\/p>\n
3. Count Connected Components<\/h3>\n
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.<\/p>\n
4. Implementation in Swift<\/h3>\n\n import Foundation\n\n \/\/ Structure to represent the graph\n class Graph {\n var adjacencyList: [[Int]]\n var visited: [Bool]\n var vertexCount: Int\n\n init(vertexCount: Int) {\n self.vertexCount = vertexCount\n self.adjacencyList = Array(repeating: [], count: vertexCount + 1)\n self.visited = Array(repeating: false, count: vertexCount + 1)\n }\n\n func addEdge(_ u: Int, _ v: Int) {\n adjacencyList[u].append(v)\n adjacencyList[v].append(u) \/\/ Undirected graph\n }\n\n func dfs(_ vertex: Int) {\n visited[vertex] = true \/\/ Mark current vertex as visited\n for neighbor in adjacencyList[vertex] {\n if !visited[neighbor] {\n dfs(neighbor) \/\/ Recursive call\n }\n }\n }\n\n func countConnectedComponents() -> Int {\n var componentCount = 0\n for vertex in 1...vertexCount {\n if !visited[vertex] {\n dfs(vertex) \/\/ New connected component found\n componentCount += 1\n }\n }\n return componentCount\n }\n }\n\n \/\/ Taking input\n let firstLine = readLine()!.split(separator: \" \").map { Int($0)! }\n let n = firstLine[0]\n let m = firstLine[1]\n let graph = Graph(vertexCount: n)\n\n for _ in 0..\n<\/section>\n\nTime Complexity<\/h2>\n
Example<\/h2>\nInput<\/h3>\n\n 5 3\n 1 2\n 2 3\n 4 5\n <\/pre>\nOutput<\/h3>\n\n 2\n <\/pre>\nIn 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.<\/p>\n<\/section>\n\nSolution Process<\/h2>\n
To solve this problem, we will implement DFS in Swift to calculate the connected components.<\/p>\n
1. Graph Representation<\/h3>\n
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.<\/p>\n
2. DFS Implementation<\/h3>\n
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.<\/p>\n
3. Count Connected Components<\/h3>\n
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.<\/p>\n
4. Implementation in Swift<\/h3>\n\n import Foundation\n\n \/\/ Structure to represent the graph\n class Graph {\n var adjacencyList: [[Int]]\n var visited: [Bool]\n var vertexCount: Int\n\n init(vertexCount: Int) {\n self.vertexCount = vertexCount\n self.adjacencyList = Array(repeating: [], count: vertexCount + 1)\n self.visited = Array(repeating: false, count: vertexCount + 1)\n }\n\n func addEdge(_ u: Int, _ v: Int) {\n adjacencyList[u].append(v)\n adjacencyList[v].append(u) \/\/ Undirected graph\n }\n\n func dfs(_ vertex: Int) {\n visited[vertex] = true \/\/ Mark current vertex as visited\n for neighbor in adjacencyList[vertex] {\n if !visited[neighbor] {\n dfs(neighbor) \/\/ Recursive call\n }\n }\n }\n\n func countConnectedComponents() -> Int {\n var componentCount = 0\n for vertex in 1...vertexCount {\n if !visited[vertex] {\n dfs(vertex) \/\/ New connected component found\n componentCount += 1\n }\n }\n return componentCount\n }\n }\n\n \/\/ Taking input\n let firstLine = readLine()!.split(separator: \" \").map { Int($0)! }\n let n = firstLine[0]\n let m = firstLine[1]\n let graph = Graph(vertexCount: n)\n\n for _ in 0..\n<\/section>\n\nTime Complexity<\/h2>\n
\n 5 3\n 1 2\n 2 3\n 4 5\n <\/pre>\nOutput<\/h3>\n
\n 2\n <\/pre>\nIn 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.<\/p>\n<\/section>\n
\n Solution Process<\/h2>\n
To solve this problem, we will implement DFS in Swift to calculate the connected components.<\/p>\n
1. Graph Representation<\/h3>\n
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.<\/p>\n
2. DFS Implementation<\/h3>\n
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.<\/p>\n
3. Count Connected Components<\/h3>\n
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.<\/p>\n
4. Implementation in Swift<\/h3>\n
\n import Foundation\n\n \/\/ Structure to represent the graph\n class Graph {\n var adjacencyList: [[Int]]\n var visited: [Bool]\n var vertexCount: Int\n\n init(vertexCount: Int) {\n self.vertexCount = vertexCount\n self.adjacencyList = Array(repeating: [], count: vertexCount + 1)\n self.visited = Array(repeating: false, count: vertexCount + 1)\n }\n\n func addEdge(_ u: Int, _ v: Int) {\n adjacencyList[u].append(v)\n adjacencyList[v].append(u) \/\/ Undirected graph\n }\n\n func dfs(_ vertex: Int) {\n visited[vertex] = true \/\/ Mark current vertex as visited\n for neighbor in adjacencyList[vertex] {\n if !visited[neighbor] {\n dfs(neighbor) \/\/ Recursive call\n }\n }\n }\n\n func countConnectedComponents() -> Int {\n var componentCount = 0\n for vertex in 1...vertexCount {\n if !visited[vertex] {\n dfs(vertex) \/\/ New connected component found\n componentCount += 1\n }\n }\n return componentCount\n }\n }\n\n \/\/ Taking input\n let firstLine = readLine()!.split(separator: \" \").map { Int($0)! }\n let n = firstLine[0]\n let m = firstLine[1]\n let graph = Graph(vertexCount: n)\n\n for _ in 0..\n<\/section>\n \n Time Complexity<\/h2>\n