https://www.acmicpc.net/problem/10451
initial
I really didn't know how to solve this.
solution
We do not need to make another separate graph 2d list because we can use the incoming list's index itself. But to make it 1-indexed instead of the default 0-indexed, we have to add 0 to the start of the list like
# for not making it 0-indexed
lst = [0] + list(map(int,input().split()))The main dfs logic is where we iterate through unvisited nodes (skip visited nodes bcos they are already part of an already accounted cycle) and go as deep as possible. Once a cycle has been detected where we encounter an already visited node, we increment cycle count. At that point, the nodes of that cycle would have been marked visited so we continue dfs search on unvisited nodes.
from collections import defaultdict
n = int(input())
for _ in range(n):
m = int(input())
visited = [False for _ in range(m+1)]
count=0
# for not making it 0-indexed
lst = [0] + list(map(int,input().split()))
def dfs(i):
visited[i]=True
node = lst[i]
if not visited[node]:
dfs(node)
for i in range(1,m+1):
if not visited[i]:
dfs(i)
count+=1
print(count)revisited jan 13th
but unlike that ^ question, each node is connected to another node so no multiple edges. So no need adj matrix and we can directly use the given list.
BTW to detect cycle, if we encounter a node that we have already visited, it is a cycle.
revisited june 7th 24
pretty straightforward, just 1 dfs will lead to 1 cycle so increment count by 1
complexity
o(v+e) time and n space? nope
The given code is using Depth-First Search (DFS) to find the number of connected components in a directed graph represented as an adjacency list. The complexity of this code can be analyzed as follows:
-
Building the adjacency list: Constructing the adjacency list takes O(m) time, where 'm' is the number of edges in the graph.
-
DFS traversal: For each connected component in the graph, a DFS traversal is performed. In the worst case, where each vertex is in a separate component, you would have to perform 'm' DFS traversals. Each DFS traversal has a time complexity of O(m) because, in the worst case, you may visit all edges.
-
Overall Time Complexity: Considering both the adjacency list construction and DFS traversals, the overall time complexity is O(m^2).
-
Space Complexity: The space complexity is O(m + n) because you are storing the adjacency list and the 'visited' array. In the worst case, the adjacency list could be of size O(m), and the 'visited' array is of size O(n).
So, the code has a time complexity of O(m^2) and a space complexity of O(m + n), where 'm' is the number of edges, and 'n' is the number of vertices in the graph.
