leetcode：冗余连接 II[并查集检查环][节点入度]

学习要点

1. 并查集检查环
2. 分类讨论

题目链接

        685. 冗余连接 II - 力扣（LeetCode）

题目描述

解法：并查集检查环

class Solution {
public:int Find_Root(vector<int>& v_root, int pos) {while (v_root[pos] > 0) {pos = v_root[pos];}return pos;}bool Is_Tree(vector<vector<int>>& edges, pair<int, int> pair1_edg_rudu2) {vector<int> v_root( edges.size() + 1, -1);for (int i = 0; i < edges.size(); i++) {if (edges[i][0] == pair1_edg_rudu2.first &&edges[i][1] == pair1_edg_rudu2.second) {continue;}int root1 = Find_Root(v_root, edges[i][0]);int root2 = Find_Root(v_root, edges[i][1]);if (root1 != root2) {v_root[edges[i][1]] = root1;} else {return false;}}return true;}vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {// 标记入度为2的点int n = edges.size();vector<int> v_find_rudu(n + 1, 0);for (int i = 0; i < edges.size(); i++) {v_find_rudu[edges[i][1]]++;}// 寻找入度为2的点int point_rudu2 = -1;for (int i = 1; i < n + 1; i++) {if (v_find_rudu[i] == 2) {point_rudu2 = i;}}// 如果不存在入度为2的点:并查集解法vector<int> v_root( edges.size() + 1, -1);if (point_rudu2 == -1) {for (int i = 0; i < edges.size(); i++) {int root1 = Find_Root(v_root, edges[i][0]);int root2 = Find_Root(v_root, edges[i][1]);if (root1 != root2) {v_root[edges[i][1]] = root1;} else {return vector<int>{edges[i][0], edges[i][1]};}}return vector<int>();}// 如果存在入度为2的点else {// 倒序寻找这个边pair<int, int> pair1_edg_rudu2;pair<int, int> pair2_edg_rudu2;bool flag1 = true;for (int i = n - 1; i >= 0; i--) {if (flag1 && edges[i][1] == point_rudu2) {pair1_edg_rudu2.first = edges[i][0];pair1_edg_rudu2.second = edges[i][1];flag1 = false;continue;}if (flag1 == false && edges[i][1] == point_rudu2) {pair2_edg_rudu2.first = edges[i][0];pair2_edg_rudu2.second = edges[i][1];break;}}bool is_pair1 = Is_Tree(edges, pair1_edg_rudu2);if (is_pair1) {return vector<int>{pair1_edg_rudu2.first,pair1_edg_rudu2.second};} else {return vector<int>{pair2_edg_rudu2.first,pair2_edg_rudu2.second};}}}
};