在冗余连接I中是无向图，无向图只要在成环的边中任意删除一条就行，用并查集可以简单解决。对于如上有向图两个实例就可以直接并查集解决。但是下面这个实例不行，如果直接用并查集删除的是【1，4】，没有保证树只有一个根节点且没有保证是有向树（顶点1被两个顶点指向）
所以解决这道题得分两种情况。
第一种是存在入度为2的顶点时，就要考虑从指向它的两条边中选择一条进行删除。对于下图这个情况就是选择删除【3，1】或者【2，1】，这里的选择是有讲究的，如果选择删除【3，1】，那么剩余的n-1个顶点和n-1个边必定构成环（用并查集可以判定）；所以选择删除【2，1】，剩余的顶点和边正好构成有向树
第二种情况是不存在入度为2的顶点，只存在入度为1的顶点，也就是官方给的实例1和2，对于这种情况其实就是冗余连接I的情形，只需要用并查集找到多余的边删除就行
class Solution {
private:vector<int> father;void init() {for(int i=1;i<father.size();i++)father[i]=i;}int find(int v) {return v==father[v]?v:father[v]=find(father[v]);}bool isSame(int u,int v) {u=find(u);v=find(v);return u==v;}void join(int u,int v) {u=find(u);v=find(v);if(u==v)return ;else {father[v]=u;}}bool isTreeAfterRemoveEdge(vector<vector<int>>& edges,int deleteIndex){this->init();for(int i=0;i<edges.size();i++){if(i==deleteIndex)continue;else {int u=edges[i][0];int v=edges[i][1];if(isSame(u,v))return false;elsejoin(u,v);}}return true;}vector<int> getRemoveEdge(vector<vector<int>>& edges){this->init();for(int i=0;i<edges.size();i++){int u=edges[i][0];int v=edges[i][1];if(isSame(u,v))return {u,v};else join(u,v);}return {};}
public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int n=edges.size();this->father=vector<int>(n+1);vector<int> inDegree(n+1,0);//存储每个顶点的入度vector<int> vec;//存储指向入度为2的顶点的边的索引下标for(int i=0;i<edges.size();i++)inDegree[edges[i][1]]++;for(int i=0;i<edges.size();i++)if(inDegree[edges[i][1]]==2)vec.push_back(i);//入度为2的顶点，指向它的两条边必有一条就是要删除的边//为了保证删除的边顺序是靠后的，先判断索引1if(vec.size()>0){if(this->isTreeAfterRemoveEdge(edges,vec[1]))return edges[vec[1]];elsereturn edges[vec[0]];}else {//没有入度为2的顶点，那么就是存在有向环return this->getRemoveEdge(edges);}}
};
