[Python] DFS (Depth-first Search) ABC157D

ABC157D

UnionFind Tree is the standard, but beginners should first master DFS. Do not use recursive functions for simple operations.

reference ABC 157 D Gentle explanation of the problem

Sample code


N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

#Adjacency list of friends
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)

#Adjacency list of blocks
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)


#Friendship group (dictionary type)
D = {}
#Group parent
parent = [-1] * N
#Visit management
visited = [False] * N

for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    #Visited stack
    stack = [root]
    #Until there are no more places to visit
    while stack:
        #Pop up visitors
        n = stack.pop()
        #Visited visitor
        visited[n] = True
        #Set parents for a group of visitors
        parent[n] = root

        #Add root friends to groups and destinations
        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)

ans = [0] * N
for iam in range(N):
    #Set up your own friendship group
    group = D[parent[iam]]
    #Remove friends and yourself from the group
    tmp_ans = len(group) - len(F[iam]) - 1
    #Remove blocks from group
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')

Recommended Posts

[Python] DFS (Depth-first Search) ABC157D
[Python] DFS (Depth-first Search) ATC001A
Algorithm in Python (depth-first search, dfs)
[Python] Binary search ABC155D
[Python] BFS (breadth-first search) ABC168D
[Python] Depth-first search and breadth-first search
[Python] ABC175D
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Write a depth-first search in Python
Depth-first search using stack in Python
[Python] DP ABC184D
[Python] DFS AGC044A
[Python] UnionFind ABC177D
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
Solve ABC168D in Python
Solve ABC167-D in Python
[Python] Interval scheduling ABC103D
Python Exercise 1-Breadth-first search
[Python] Search (itertools) ABC167C
[Python] Cumulative sum ABC186D
[Python] Search (NumPy) ABC165C
Binary search (python2.7) memo
Solve ABC159-D in Python
python bit full search
Linear search in Python
Binary search with python
Binary search with Python3
Search Twitter using Python
[Python] Dynamic programming ABC015D
Binary search in Python (binary search)
[Python] Cumulative sum ABC179D
Search for strings in Python
Breadth-first search / bidirectional search (Python version)
Search algorithm using word2vec [python]
Homebrew Python --Youtube Search Program
ABC161D Lunlun Number with python3
[At Coder] Solve a typical problem of depth-first search (DFS)
Binary search in Python / C ++
Algorithm in Python (binary search)
Full bit search with Python
Search engine work with python
Search twitter tweets with python
[Python] BFS (breadth-first search) ABC007C
Streamline web search with python
Depth-first search (non-recursive type) and lower limit pruning method (Python edition)
[Python algorithm] A program that outputs Sudoku answers from a depth-first search
Algorithm in Python (breadth-first search, bfs)
Write a binary search in Python
[Python] How to derive nCk (ABC156-D)
Learn search with Python # 2bit search, permutation search
Breadth-first search (BPF) Maybe understood (python)
Master linear search! ~ Python implementation version ~
(Python) ABC162-D Consideration log and solution
Reproduce One-Touch Search on Python 3.7.3. (Windows 10)
Python 2-minute search and its derivation