[백준] 9372번: 상근이의 여행

https://www.acmicpc.net/problem/9372

initial

I am always weak at tree questions so I need to practice these. So the question said it is a connected graph so all the nodes are guaranteed to be connected with at least 1 edge. There will be a cycle cuz you can revisit a node more than once, as mentioned in the question, so the graph will look something like this in this link.

https://ku-hug.tistory.com/133

So each plane is effectively an edge that links 2 nodes together. To visit all nodes in that graph with minimal traversal of edges, it is the spanning tree.

What is a spanning tree? It is a acyclical subgraph of a connected graph and is a subset of all vertices and edges in a graph. Subset means selecting some, but not necessarily all, vertices and edges of a given graph. So it is like a more purpose-focused graph.

So a spanning tree links all n nodes and since there are no cycles, it has n-1 edges. So the answer is just n-1 lol

Or if you do dfs from node 1 and increment count via 1 as you traverse deeper with dfs, you can get the same ans. I have been doing too much backtracking so I was wrongly gonna do dfs on each node but you dont need to do that. Cuz dfs naturally covers all nodes that is connected to starting node.

solution

from collections import defaultdict
import sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
    graph = defaultdict(list)
    n, m = map(int, input().split())
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    visited = [False for _ in range(n + 1)]

    def dfs(node, count):
        visited[node] = True
        for n in graph[node]:
            if not visited[n]:
                count = dfs(n, count + 1)
        return count

    val = dfs(1, 0)
    print(val)

revisited jan 18th 2024

so i didnt get the question's plane 종류 cuz the input just gave like from city 1 to city 2. But it is considered that each traversal from any city to any city is taking plane of each type. So there is no same plane anywhere else except from a to b and vice versa.

So since it is a connected graph, we just return n-1 edges, which effectively connects all nodes with no cycle.

Or with dfs, once we reach the end of dfs traversal, we return to our call stack's dfs and since we are returning count as we traverse back the call stack, the count variable is updated with this return value. Just slowly imagine in your head from the base case all the way back to starting point.

complexity

v+e time? and n space? for space it is v+e cuz we are making adj list

The time and space complexity of this code depends on the size of the input graph, which has n nodes and m edges.

Time Complexity:

1. Constructing the graph takes O(m) time as you iterate through the m edges.
2. The depth-first search (DFS) algorithm runs in O(n + m) time because it visits each node at most once (O(n)) and each edge once (O(m)).

Overall, the time complexity of the code is O(m) for graph construction and O(n + m) for DFS, so the dominant factor is usually the DFS part.

Space Complexity:

1. The graph is represented using an adjacency list, which requires O(n + m) space to store the nodes and edges.

2. The visited list has a space complexity of O(n), as it keeps track of whether each node has been visited.

3. The recursive stack for DFS can have a space complexity of O(n), in the worst case, when the graph is a linear chain.

Overall, the space complexity is O(n + m) due to the graph representation and the visited list.