109.冗余连接II

不好做：

1.入度为2：看删哪条边可以形成树，而不是环（因为只有两种可能，一个树，一个环）

2.没有入度为2的点：有向环，删最后形成环的那条

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> father(1001, 0);

void init() {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}

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;
    }
    father[v] = u;
}

bool isTreeAfterRemoveVec(const vector<vector<int>>& edges, int v) {
    init();
    for (int i = 0; i < n; i++) {
        if (i == v) {
            continue;
        }
        if (isSame(edges[i][0], edges[i][1])) {
            return false;
        }
        join(edges[i][0], edges[i][1]);
    }

    return true;
}

void getRemoveEdge(const vector<vector<int>>& edges) {
    init();
    for (int i = 0; i < n; i++) {
        if (isSame(edges[i][0], edges[i][1])) {
            cout << edges[i][0] << " " << edges[i][1];
            return;
        }
        join(edges[i][0], edges[i][1]);
    }
}

int main() {

    // int N;
    cin >> n;
    // init(); //1111
    
    // n = 3;
    // vector<vector<int>> grid;
    // grid = {
    //     {1,2},
    //     {1,3},
    //     {2,3}
    // };


    vector<vector<int>> edges;
    vector<int> degrees(n+1, 0);

    int s, t;
    for(int i=0;i<n;i++) {
        cin >> s >> t;
        // s = grid[i][0];
        // t = grid[i][1];

        edges.push_back({ s,t });
        degrees[t]++;

    }

    //计算入度
    vector<int> vec;
    for (int i = 0; i < n; i++) {
        //cout << degrees[edges[i][1]] << " ";
        if (degrees[edges[i][1]] == 2) {
            vec.push_back(i);
        }
    }
    
    //情况1：入度为2，看删哪个
    if (vec.size() > 1) {
        if (isTreeAfterRemoveVec(edges, vec[1])) {
            cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;
        }
        else {
            cout << edges[vec[0]][0] << " " << edges[vec[0]][1] << endl;
        }
        return 0;
    }

    //情况2：有向环
    getRemoveEdge(edges);

    return 0;
}