https://leetcode-cn.com/problems/redundant-connection-ii/
对于有向图的树，如果增加一条有向边，则会出现两种情况
第一种为形成一个点有两个father
1.有有向环，无环
第二种为有环
class Solution {
private:
static const int N = 1010; // 如题：二维数组大小的在3到1000范围内
int father[N];
int n; // 边的数量
// 并查集初始化
void init() {
for (int i = 1; i <= n; ++i) {
father[i] = i;
}
}
// 并查集里寻根的过程
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return ;
father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
// 在有向图里找到删除的那条边，使其变成树
vector<int> getRemoveEdge(const vector<vector<int>>& edges) {
init(); // 初始化并查集
for (int i = 0; i < n; i++) { // 遍历所有的边
if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
return edges[i];
}
join(edges[i][0], edges[i][1]);
}
return {};
}
// 删一条边之后判断是不是树
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
init(); // 初始化并查集
for (int i = 0; i < n; i++) {
if (i == deleteEdge) continue;
if (same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
return false;
}
join(edges[i][0], edges[i][1]);
}
return true;
}
public:
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int inDegree[N] = {0}; // 记录节点入度
n = edges.size(); // 边的数量
for (int i = 0; i < n; i++) {
inDegree[edges[i][1]]++; // 统计入度
}
vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
// 找入度为2的节点所对应的边，注意要倒叙，因为优先返回最后出现在二维数组中的答案
for (int i = n - 1; i >= 0; i--) {
if (inDegree[edges[i][1]] == 2) {
vec.push_back(i);
}
}
// 处理图中情况1 和 情况2
// 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
if (vec.size() > 0) {
if (isTreeAfterRemoveEdge(edges, vec[0])) {
return edges[vec[0]];
} else {
return edges[vec[1]];
}
}
// 处理图中情况3
// 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
return getRemoveEdge(edges);
}
};
作者：carlsun-2
链接：https://leetcode-cn.com/problems/redundant-connection-ii/solution/685-rong-yu-lian-jie-iibing-cha-ji-de-ying-yong-xi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。