[백준] 5567번: 결혼식

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

initial

I first thought it is a topological sort question until I drew the first example on paper. It showed an undirected cyclic graph but topo sort needs directed acyclic graph.

So I rethought and figured dfs impl with depth where if depth ==2, we return because we dont wanna traverse beyond depth of 2 as we are only searching up to friends of friends, but not friend of friend of friend.

I also thought it is a directed cyclic graph but an input can be given like
3
2
2 3
1 3

so if we only mark it as directed (by marking graph[a].append(b) and not the other way) and do dfs from 1, we will get invalid answer of 0. So it is undirected

solution

from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = defaultdict(list)

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)]
ans = [False for _ in range(n + 1)]
visited[1] = True

def dfs(node, depth):
    if depth == 2:
        return
    for a in graph[node]:
        if not visited[a]:
            ans[a] = True
            visited[a] = True
            dfs(a, depth + 1)
            visited[a] = False
dfs(1,0)
count = 0
for i in ans:
    if i:
        count += 1
print(count)

complexity

n time and space?

nope when we build the graph, it is m time. Dfs takes m time and the traversal after dfs takes n time. so it is m+n time.

The provided code performs a depth-first search (DFS) on a graph and counts the number of nodes that are within 2 levels from the starting node. Here's the complexity analysis:

Time Complexity:

• Building the graph by iterating through the edges takes O(m) time, where 'm' is the number of edges.
• The DFS traversal is performed on the graph. In the worst case, each edge is traversed once, leading to O(m) operations.
• After the DFS traversal, there is a loop that iterates through the ans list, which contains all nodes visited during the DFS. This loop takes O(n) time, where 'n' is the number of nodes.

Overall, the time complexity is O(m + m + n), which simplifies to O(m + n).

Space Complexity:

• The graph is represented using a defaultdict of lists, which consumes additional space proportional to the number of edges and nodes, resulting in a space complexity of O(m + n).
• Additional lists visited and ans are used to keep track of visited nodes, each consuming O(n) space.
• The recursive DFS function uses the call stack, which can grow up to the depth of the recursion. In the worst case, the recursion depth can be 2, so the space complexity due to the call stack is O(2), which is constant.

Overall, the space complexity is O(m + n).

In summary, the time complexity of the code is O(m + n), where 'm' is the number of edges and 'n' is the number of nodes. The space complexity is also O(m + n).