来到题我是挂了求解

给定一个pair list
(a,b), (a,c), (b,d), (c,d), (e,f),

返回2个set
这两个set中， 在源pair list中的 任意一个pair中2个元素，
不可以同时出现在最终的同一个set中
题目假设最终可以划分为2个set,一定存在划分结果

完全蒙圈，最开始想到的是遍历，但无法确定如何分配，可能很后面的pair，才能确定当前的划分
只给了DFS暴力

所有pair当作edges建图，某个node的所有相邻nodes一定属于同一个set。遍历一遍确定两个set，dfs/bfs/uf都可以，O(N)/O(N)

bipartite graph

https://leetcode-cn.com/problems ... fen-tu-by-girapath/

fr42k 发表于 2021-6-3 02:45
bipartite graph

https://leetcode-cn.com/problems/is-graph-bipartite/solution/ran-se-fa-xiang-jie- ...

so 这是烙印套了壳的二分图变种？
当时没想到这点

这样的点也叫independent set.
因为保证了只有两个，所以也可以看作bipartite graph.

这题是染色问题吗？BFS走一遍？

o彩蝶寻梦o 发表于 2021-6-6 10:36
这题是染色问题吗？BFS走一遍？

二分图的变种
刷题不精 中招