Assume I have pair of integers like: [(1,2), (3,4), (2,3), (3,5), (7, 8), (7,9)] and I would like to sort the pairs into unique groups based on connected elements amongst them i.e. if elements share a common element with one other pair in the same group, then they should be put into the same group. So in the example above, we will end up with two groups:

Group1: (1,2), (2,3), (3,4), (3,5)

Group2: (7,8), (7, 9)

The key is that there should be at least one reference that appears in a previous pair (i.e. this is the definition of connected pairs), and this previous pair can be any one of the previous pairs, and not the one directly preceding it. If there are no "connected pairs", then the pair should be separated to a new group by itself

I understand that this can be done with graphs, but would anyone be able to suggest the most efficient, and easy to implement solution in C ?

Thanks!

CodePudding user response：

Assumptions: Pairs are ordered. (a,a),(a,b),(b,a) is a valid input.

Yes this problem can be solved using an undirected graph.

For each given pair (a, b), create an undirected edge between a and b. Now traverse this graph to find its connected components. Remember the component of each node, eg. by coloring them. Finally for all input pairs check the component they belong to (aka color) and add it to that group. Sort each group individually and output.

Time complexity

Let n be the number of pairs in input.

Traversal: O(n). There are O(n) nodes and O(n) edges in the graph we built. For given C code below - we will visit each edge at most twice (due to undirected graph). Any already visited node is returned from the first line itself, which happens for each incident edge on that node. Count of such incident edges over all nodes is O(n).

Sorting: O(n * log n) since maximum size of group can be O(n)

Total: O(n * log n)

Sample code in C :

(This code targets C 17 and above)

I am storing the graph as an adjacency list adj and using depth first traversal dfs. Assuming the input integers fit into an int, you can also use vectors instead of unordered_maps if they are further bounded.

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm> 

using namespace std;
       
unordered_set<int> vis;
unordered_map<int, vector<int>> adj;

void dfs(int u, vector<int>& cur_group) {
    if (vis.count(u)) return;
    vis.insert(u);
    cur_group.push_back(u);
    for (auto v: adj[u]) {
        dfs(v, cur_group);
    }
};

int main() {
    vector<pair<int, int>> input = {{4,3},{1,9},{7,9},{2,4},{3,2},{9,7},{9,9}};

    // create undirected graph
    for (auto [u, v]: input) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int component_count = 0;
    unordered_map<int, int> color;
    // traverse all nodes and color all nodes reachable.
    for (auto [u, v]: input) {
        // If u is traversed v must be traversed as they are adjacent
        if (vis.count(u) == 0) {
            vector<int> cur_group;
            dfs(u, cur_group);
            for (int v: cur_group) {
                color[v] = component_count;
            }
            component_count  ;
        }
    }

    // push input pairs into their corresponding color component
    vector<vector<pair<int, int>>> components(component_count);
    for (auto p: input) {
        components[color[p.first]].push_back(p);
    }

    // sort and output each color component separately
    for (auto& component: components) {
        sort(component.begin(), component.end());
        for (auto [u, v]: component) {
            cout << '(' << u << ',' << v << "),";
        }
        cout << endl;
    }

    return 0;
}

Output:

(2,4),(3,2),(4,3),
(1,9),(7,9),(9,7),(9,9),

CodePudding user response：

O(n^2) solution, this will give you the number of groups, the code can be modified to get the groups values

public static void main(String[] args) {

    int[][] input = {{1, 2}, {3, 4}, {2, 3}, {3, 5}, {7, 8}, {7, 9}};

    int count = 0;

    Set<Integer> seen = new HashSet<>();

    for (int i = 0; i < input.length; i  ) {

        if (seen.contains(i)) {
            continue;
        }

        Set<Integer> aGroup = new HashSet<>();
        aGroup.add(input[i][0]);
        aGroup.add(input[i][1]);

        count  ;
        seen.add(i);

        for (int j = i   1; j < input.length; ) {

            if (!seen.contains(j) && (aGroup.contains(input[j][0]) || aGroup.contains(input[j][1]))) {
                seen.add(j);
                aGroup.add(input[j][0]);
                aGroup.add(input[j][1]);

                j = i   1;
            } else {
                j  ;
            }
        }
    }

    System.out.println(count);
}