https://leetcode.com/contest/leetcode-weekly-contest-51/problems/redundant-connection/

[Implementation idea]:
input edge (a, b), current set group = set
(1.1): if a & b locate in the same set S, find loop.
(1.2): if a & b locate in different set S1 & S2, make a new set S3 consists of S1 & S2 (S3 is the union of S1 & S2).
(2): if a(or b) locates in a set S but b(or a) has not appeared yet, add b to S. 
(3): if both a & b have not appeared yet, create a new set S with members a & b.

#include <iostream>
#include <set>
#include <vector>

using namespace std;

class Solution {
public:
    void dump(vector<set<int>> &connected) {
        set<int>::iterator it;
        for (int i = 0; i < connected.size(); i++) {
            for (it = connected[i].begin(); it != connected[i].end(); it++) {
                printf("[%d %d]\n", i, *it);
            }
        }
        printf("\n\n");
    }

    int getSetNumber(vector<set<int>> &connected, int vertex) {
        for (int i = 0; i < connected.size(); i++) {
            if (connected[i].find(vertex) != connected[i].end()) {
                return i;
            }
        }
        return -1;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {

        vector<set<int>> connected;

        for (int i = 0; i < edges.size(); i++) {
            int vertexOne = edges[i][0];
            int vertexTwo = edges[i][1];
            
            int setOne = getSetNumber(connected, vertexOne);
            int setTwo = getSetNumber(connected, vertexTwo);

            if ((setOne != -1) && (setTwo != -1)) {
                if (setOne == setTwo) {
                    return edges[i];
                } else {
                    connected[setOne].insert(connected[setTwo].begin(), connected[setTwo].end());
                    vector<set<int>>::iterator it = (connected.begin() + setTwo);
                    connected.erase(it);
                }
            } else if ((setOne == -1) && (setTwo == -1)) {
                set<int> group;
                group.insert(vertexOne);
                group.insert(vertexTwo);
                connected.push_back(group);
            } else {
                if (setOne == -1) {
                    connected[setTwo].insert(vertexOne);
                } else /*(setTwo == -1)*/{
                    connected[setOne].insert(vertexTwo);
                }
            }
        }
        return {};
    }
};

int main()
{
    vector<vector<int>> input;
    input.push_back({1, 2});
    input.push_back({2, 3});
    input.push_back({3, 4});
    input.push_back({1, 4});

    Solution solution;
    solution.findRedundantConnection(input);
    return 1;
}