额外 - 杭电 - 畅通工程

题目：畅通工程

本质：计算无向图的连通分量

输入：int N = 城镇数
list input_list = 城镇之间的联通关系

方法1：并查集

class FindUnion:
    def __init__(self, n):
        self.pre = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

    def find(self, i):
        if self.pre[i] == i:
            return i
        self.pre[i] = self.find(self.pre[i])
        return self.pre[i]

    def join(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] > self.rank[root_y]:
            self.pre[root_y] = root_x
        else:
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_y] += 1
            self.pre[root_x] = root_y

    def handle_input(self, _list):
        for i in _list:
            self.join(i[0], i[1])

    def calc_how_many_road_we_need(self):
        repeat_count = 0
        already_appeared = {}
        for item in self.pre[1:]:
            if item not in already_appeared:
                repeat_count += 1
                already_appeared[item] = True
        return repeat_count - 1


if __name__ == "__main__":
    n = 4
    input_list = [[1, 3], [4, 3]]
    fu = FindUnion(n)
    fu.handle_input(input_list)
    print(fu.calc_how_many_road_we_need())

方法2：DFS

class Graph:
    def __init__(self, _n, _list):
        self.visit = [0 for _ in range(_n)]
        self.maze = []
        for x in range(_n):
            temp = []
            for y in range(_n):
                if x == y:
                    temp.append(1)
                else:
                    temp.append(0)
            self.maze.append(temp)
        for i in _list:
            self.maze[i[0]-1][i[1]-1] = 1
            self.maze[i[1]-1][i[0]-1] = 1
        print(self.maze)

    def dfs(self, i):
        if self.visit[i] == 1:
            return
        self.visit[i] = 1
        for j in range(len(self.maze)):
            if self.maze[i][j]:
                self.dfs(j)

    def travel(self):
        count = 0
        for i in range(len(self.maze)):
            if self.visit[i] == 0:
                self.dfs(i)
                count += 1
        return count - 1


if __name__ == "__main__":
    n = 4
    input_list = [[1, 3], [3, 4]]
    g = Graph(n, input_list)
    print(g.travel())