2024-06-30
1579. Remove Max Number of Edges to Keep Graph Fully Traversable
Alice and Bob have an undirected graph of n nodes and three types of edges:
Type 1: Can be traversed by Alice only.
Type 2: Can be traversed by Bob only.
Type 3: Can be traversed by both Alice and Bob.
Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.
Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.
又是寫不出來偷看答案還要卡好久的一天
題目需求是把盡量多的edge 砍掉
所以就會需要知道把某一條edge 丟掉
是不是還能連成一塊
或者是反過來想
要連成一塊需不需要這條edge
其中一個解答的做法是用 disjoint set Union find
大概是某個資料結構還是演算法上課教過然後考完試就忘了的東西
每個disjoint set 會用tree表示
每棵tree 用root做代表
兩個element看往回找的root 是否相同就能知道是不是屬於同一個set
而要合併就是把其中一個的root接到另一個的root 下
首先把所有node當成disjoint set
然後開始處理edge
兩個node 有edge 相連的話就表示屬於同一個set
用Union 把兩個合併
在做Union 的時候順便檢查這兩個node是不是本來就已經在同一個set了
如果是新的 表示需要這條 edge
如果已經在一起了 表示這條edge 是多的
最後如果有人的set 數超過一表示不能走完
而若能走完 總edge 數與必要的edge 數相煎就是答案