[Programmers] 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

Initial approach

This was similiar to [Programmers] 네트워크 problem so I tried solving it through dfs where I remove that wire from graph and do dfs search on that modified graph.

my wrong code:

from collections import deque,defaultdict
import math


def solution(n, wires):
  graph = defaultdict(list)
  for wire in wires:
    graph[wire[0]].append(wire[1])
    graph[wire[1]].append(wire[0])
  print(graph)
  visited = [False for _ in range(n+1)]
  count =n
  for wire in wires:
    graph[wire[0]].remove(wire[1])
    graph[wire[1]].remove(wire[0])
    for i in range(1,len(graph)+1):
      if not visited[i] and graph[i]:
        count = min(count, dfs(visited, graph, i))
      # Restore the removed edges
    graph[wire[0]].append(wire[1])
    graph[wire[1]].append(wire[0])
  print(count)
  return count

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

But the problem is that removing wire from my graph resulted in empty list for a given key and dfs still traverses through that. So that is the wrong part. I needed a different way to mark the disconnection, apart from this remove() way.

Also another problem was using the same visited list each time I iterated through wires. I should have instantiated a new one each time for each wire.

Solution

For the first problem, I googled and some used a 2d list like this check_link. (or you can create graph each time you iterate through wires but inefficient)

# 없앤 간선인지 아닌지 체크 값이 들어있는 리스트
check_link = [[True]*(n+1) for _ in range(n+1)]

for a, b in wires:
  visited = [False]*(n+1)

  check_link[a][b] = False # a-b 간선 끊기
  cnt_a = DFS(a, graph, visited, check_link)
  cnt_b = DFS(b, graph, visited, check_link)
  check_link[a][b] = True # a-b 간선 다시 연결

This check_link will check if there is a disconnection from a to b, which will be marked as False if there is a disconnection. And in our DFS search, we only proceed deeper if

• check_link[a][b] = True (there is a connection)
• not visited[node] (haven't visited this node before)

We do 2 DFS search - 1 from a and 1 from b. During DFS, we will be using the same visited list and marking some nodes as visited. If the other DFS search stumbles upon an already visited node or if it is not visited but the connection to that point from current node is False (disconnected) then we can't visit that node and increment count.

And importantly, once we finish our DFS search, we have to connect the disconnection back (from False to True).

from collections import defaultdict
def solution(n, wires):
    ans = int(10e9)
    graph = defaultdict(list)
    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])
    
    check_link = [[True for _ in range(n+1)] for _ in range(n+1)]
    
    def dfs(i,visited):
        visited[i]=True
        count =1
        for node in graph[i]:
            if not visited[node] and check_link[i][node]:
                count += dfs(node,visited)
        return count
                
    for wire in wires:
        visited=[False for _ in range(n+1)]
        check_link[wire[0]][wire[1]]=False
        count1 = dfs(wire[0],visited)
        count2 = dfs(wire[1],visited)
        check_link[wire[0]][wire[1]]=True
        ans = min(abs(count1-count2),ans)
        
    return ans

Or you can make it more nice by taking dfs function outside

def solution(n, wires):
    graph = defaultdict(list)
    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])
    print(graph)

    check_link = [[True for _ in range(n+1)] for _ in range(n+1)]
    count = n
    for wire in wires:
        visited = [False for _ in range(n+1)]
        check_link[wire[0]][wire[1]] = False
        count1= dfs(visited,check_link,graph,wire[0])
        count2=dfs(visited,check_link,graph,wire[1])
        count = min(abs(count1-count2),count)
            # Restore the removed edges
        check_link[wire[0]][wire[1]] = True
    print(count)
    return count

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

revisited [13th jan] well-explained by me

Complexity

The time complexity of this solution is O(N^2), and the space complexity is O(N^2), where N is the number of nodes or vertices in the graph.

Here's a breakdown of the complexities:

1. Time Complexity (O(N^2)):

   • Building the graph dictionary by iterating through wires takes O(N) time because there are at most N edges.
   • The DFS function is called once for each pair of vertices in wires, so it can be called at most N times.
   • Inside the DFS function, there's a loop that iterates through the neighbors of a vertex. In the worst case, where all nodes are connected to each other, this loop will run N-1 times.
   • Therefore, the overall time complexity is O(N) O(N) (N-1) = O(N^2).

2. Space Complexity (O(N^2)):

   • The graph dictionary stores adjacency lists for each node, and in the worst case, where all nodes are connected to each other, it will have O(N^2) entries.
   • The check_link matrix also has N^2 elements.

So, both time and space complexities are quadratic in terms of the number of nodes (N).

BFS and union find version (union find problem actually)