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 数相煎就是答案