\n In modern algorithm problem solving, graphs are a very important and fundamental data structure. In this article, we will explain the representation of graphs and learn how to solve related problems using C++.\n <\/p>\n
\n A graph is a data structure composed of vertices and edges, which is useful for expressing various relationships. For instance, graphs can be utilized in various scenarios such as relationships between users in a social network, connections between cities in a road network, and links between web pages.\n <\/p>\n
\n Graphs are generally represented in two ways: Adjacency Matrix and Adjacency List. Each method has its own advantages and disadvantages, so it is important to choose the appropriate method according to the nature of the problem.\n <\/p>\n
\n An adjacency matrix is a way to represent a graph using a two-dimensional array. The size of the matrix is V x V (where V is the number of vertices), and each element of the matrix (i, j) indicates whether there is an edge between vertex i and vertex j.\n <\/p>\n
\n \/\/ Declaration of adjacency matrix in C++\n const int MAX = 100; \/\/ Maximum number of vertices\n int adj[MAX][MAX]; \/\/ Adjacency matrix\n int V; \/\/ Number of vertices\n <\/code><\/pre>\n\n The advantage of an adjacency matrix is that it allows you to check the existence of a specific edge in O(1) time. However, in terms of memory, it uses the square of V, making it inefficient when there are many vertices but few edges.\n <\/p>\n
2. Adjacency List<\/h3>\n
\n An adjacency list is a method that uses a list of vertices connected to each vertex. This is more suitable for sparse graphs.\n <\/p>\n
\n \/\/ Declaration of adjacency list in C++\n #include \n #include \n using namespace std;\n\n vector adj[MAX]; \/\/ Adjacency list\n int V; \/\/ Number of vertices\n <\/int><\/iostream><\/vector><\/code><\/pre>\n\n The adjacency list uses memory more efficiently and requires O(E) time to traverse the list of edges.\n <\/p>\n
Problem: Finding Connected Components<\/h2>\n
\n In this problem, you need to find all components that are interconnected in the given directed graph. In other words, you need to identify the set of vertices that can be reached starting from a single vertex.\n <\/p>\n
Problem Description<\/h3>\n
\n Given the number of vertices V and the number of edges E, with each edge provided as a pair of two vertices, write a program to find and output all connected components in this graph.\n <\/p>\n
Input Format<\/h3>\n\n- First line: Number of vertices V (1 \u2264 V \u2264 1000)<\/li>\n
- Second line: Number of edges E (0 \u2264 E \u2264 10000)<\/li>\n
- Next E lines: Each line represents an edge in the form (u, v)<\/li>\n<\/ul>\n
Output Format<\/h3>\n
\n Output the number of connected components and the vertices of each component in ascending order.\n <\/p>\n
Problem-solving Process<\/h2>\n
\n To solve the problem, we will use an adjacency list to store the graph and find connected components using depth-first search (DFS).\n <\/p>\n
Step 1: Constructing the Adjacency List<\/h3>\n
\n First, we need to take the input and construct the adjacency list. We will input the number of vertices and edges and complete the list representing the relationships through each edge.\n <\/p>\n
Step 2: Finding Connected Components with DFS<\/h3>\n
\n Whenever a search occurs, we mark the visited vertex, and repeat this until there are no more vertices to visit, thereby finding the components. The implementation of DFS can be easily done recursively.\n <\/p>\n
\n #include \n #include \n #include \n\n using namespace std;\n\n vector adj[1001]; \/\/ Adjacency list\n bool visited[1001]; \/\/ Visit check\n vector> components; \/\/ Store connected components\n\n void dfs(int v, vector &component) {\n visited[v] = true; \/\/ Mark as visited\n component.push_back(v); \/\/ Add to the component\n\n for (int u : adj[v]) {\n if (!visited[u]) {\n dfs(u, component); \/\/ Recursion\n }\n }\n }\n\n int main() {\n int V, E;\n cin >> V >> E;\n\n for (int i = 0; i < E; i++) {\n int u, v;\n cin >> u >> v; \/\/ Input edge\n adj[u].push_back(v); \/\/ Construct adjacency list\n adj[v].push_back(u); \/\/ Assuming an undirected graph\n }\n\n \/\/ Finding connected components for each vertex\n for (int i = 1; i <= V; i++) {\n if (!visited[i]) {\n vector component;\n dfs(i, component); \/\/ DFS search\n components.push_back(component); \/\/ Store found component\n }\n }\n\n \/\/ Output results\n cout << components.size() << \"\\n\"; \/\/ Number of connected components\n for (const auto &component : components) {\n sort(component.begin(), component.end()); \/\/ Sort the component\n for (int v : component) {\n cout << v << \" \"; \/\/ Output vertices\n }\n cout << \"\\n\";\n }\n\n return 0;\n }\n <\/int><\/int><\/vector<\/int><\/algorithm><\/vector><\/iostream><\/code><\/pre>\n\n The above code implements the logic to find and output connected components from the input graph. It sorts and outputs each component in ascending order.\n <\/p>\n
Conclusion<\/h2>\n
\n We have examined the representation of graphs and the process of solving problems using DFS. Graphs play an important role in various algorithm problems, and learning them is fundamental to achieving good results in coding tests. I hope this course enhances your basic understanding of graphs and your problem-solving skills.\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"