How to group nodes that have common edges from given string of pairs?

I'm pretty confused by your code. A reasonable graph representation is a map from node to set of adjacent nodes, i.e. those connected by a directed edge. If the graph is undirected, then there will be mirrored mappings: from A -> {..B..} and B -> {..A..} for each edge A, B.

To implement this you want something like:

class GraphForFun {
 static void addDirectedEdge(Map<Integer, Set<Integer>> graph, int a, int b) {
    Set<Integer> adjacent = graph.get(a);
    if (adjacent == null) {
      adjacent = new HashSet<>();
      graph.put(a, adjacent);
    }
    adjacent.add(b);
  }

  static Map<Integer, Set<Integer>> getGraph(List<String> edges) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (String edge : edges) {
      String vertexNumbers[] = edge.split("\\s+");
      int a = Integer.parseInt(vertexNumbers[0]);
      int b = Integer.parseInt(vertexNumbers[1]);
      addDirectedEdge(graph, a, b);
      addDirectedEdge(graph, b, a); // Remove if graph is directed.
    }
    return graph;
  }

  public static void main(String[] args) {
    String[] edges = {"6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16"};
    Map<Integer, Set<Integer>> graph = getGraph(Arrays.asList(edges));
    System.out.println(graph);
  }
}

This prints

{16=[1, 15], 1=[16], 5=[9], 6=[11], 9=[5, 11, 15], 11=[6, 9], 12=[14], 13=[15], 14=[12], 15=[16, 9, 13]}

From what I've understood, you basically track the islands in your graph. Since I'm not fluent with Java, I'll write a simple algorithm to solve your purpose.

1. Create a graph[], where each key maps to an adjacency list. For every i j in your input, append j to graph[i] and i to graph[j].
2. Create a map output, which we will now fill.
3. Start a DFS from the first node (or any node that you prefer). The DFS function would be like

dfs (node, source):
    if not visited node:
        visited[node] = true
        append node to output[source]
        for neighbour in graph[node]:
            dfs(neighbour, source)

4. Check if any node is unvisited. If you find such node, you just have to call dfs (node, node).

This will give you the desired map of islands you need.

What you want is to find the connected components (more specifically apparently only their size)

You may lookup for better algorithms.

Since learning let's rediscover some wheel:

• If there is an edge between two nodes, link them
• When linking two nodes, one is the eater and the other is the eaten: link every node of the eaten's links to the eater

e.g

a1    b1
|     |
a2    b2
|     |
A     B

• a1,...a2, are nodes linked to node A
• b1,...b2, are nodes linked to node B

when merging A and B, (e.g) say A is the eater, B the eaten then link b1, b2, B to A

a1    
|     
a2 - b1 - b2 - b // notice B lowercase since belongs to "group" A
|     
A

Below a js implem (java would take me too much time). Hopefully it is close enough to pseudocode ?

/*
  strToGroupId     groupIdToGroup 
  _____________________________________
  strA ------> gA -----> { strA }
  strB --v
  strC --+---> gB -----> { strB, strC }

*/
strToGroupId = new Map // str -> int
groupIdToGroup = new Map // int -> Set<str>
const link = ([strA, strB]) => {
  // assign a group if new node
  if (!strToGroupId.has(strA)) {
    strToGroupId.set(strA, strA),
    groupIdToGroup.set(strA, new Set([strA]))
  }
  if (!strToGroupId.has(strB)) {
    strToGroupId.set(strB, strB),
    groupIdToGroup.set(strB, new Set([strB]))
  }

  const gA = strToGroupId.get(strA)
  const gB = strToGroupId.get(strB)

  if (gA === gB) return
  // need to merge
  const eaters = groupIdToGroup.get(gA)
  const eatens = groupIdToGroup.get(gB)
  for (const n of eatens) {
    eaters.add(n)
    strToGroupId.set(n, gA) // the eateN now links to gA instead of gB
  }
  groupIdToGroup.delete(gB) // gB does not exist anymore
}
const data = ["6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16"]
data.map(x => x.split(' ')).forEach(link)
console.log([...groupIdToGroup.values()].map(aSet => [...aSet]))

I am going to suggest another solution. The first observation we need to make, is that we don't really want to get a Map<Integer, Set<Integer>>. The key, 5 for example, is no different than any other node. The reason it is the key, is only because it is prior in the list. Therefore I am going to build:

Set<Set<Integer>> map

Where for every 2 sets in this set, they have empty intersection.

The algorithm

1. For every edge:

   1. Extract 2 vertices.

   2. build set with this 2 nodes.

   3. Go over all existing sets:

      1. Aggregate all sets that has one of the two vertices into a new set.
      2. Remove all sets from previous step.
      3. Add the aggregated set.

The implementation

public static void process(List<String> input) {
    Set<Set<Integer>> map = new HashSet<>();
    for (String in : input) {
        String[] arr = in.split(" ");
        int a1 = Integer.parseInt(arr[0]);
        int a2 = Integer.parseInt(arr[1]);

        Set<Integer> aggregatedSet = new HashSet<>();
        Set<Set<Integer>> setsToRemove = new HashSet<>();
        aggregatedSet.add(a1);
        aggregatedSet.add(a2);
        for (Iterator<Set<Integer>> it = map.iterator(); it.hasNext(); ) {
            Set<Integer> currentNodes = it.next();
            if (currentNodes.contains(a1) || currentNodes.contains(a2)) {
                aggregatedSet.addAll(currentNodes);
                setsToRemove.add(currentNodes);
            }
        }

        map.removeAll(setsToRemove);
        map.add(aggregatedSet);
    }
    System.out.println(map);
}

The following:

List<String> edges = Arrays.asList("6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16");
process(edges);

Will output:

[[12, 14], [16, 1, 5, 6, 9, 11, 13, 15]]

And the following:

List<String> edges = Arrays.asList("40 22","60 6","22 39","43 40","22 55","48 57","42 41","22 57","6 42","33 74","70 46","4 11","6 28","22 79","61 34","77 40","4 8","72 26","62 50","72 51","1 79","34 29","77 41","2 48","43 2","62 45","43 17","19 33","76 4","35 54");
process(edges);

Will output:

[[1, 2, 6, 39, 40, 41, 42, 43, 77, 79, 48, 17, 22, 55, 57, 28, 60], [4, 8, 11, 76], [70, 46], [51, 72, 26], [35, 54], [34, 29, 61], [50, 45, 62], [33, 19, 74]]

Interesting problem. My take on this was to build an adjacency list (map of the node ids and their immediate children) then search that to find the common paths. A map visitedAndGroupId (ugly name!) is used to both keep track of visited nodes and which group they belong to. The key is the original node and the value is a group id. Finally we iterate over the visited map and build out the groups and their contents so as to prepare the output.

private static HashMap<Integer,Set<Integer>> adjacencyList;
    private static Map<Integer, Integer> visitedAndGroupId = new HashMap<>();
    private static int groupId = 0;

    public static void main(String[] args) {
        List<String> pairs = Arrays.asList("6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16");
        adjacencyList = buildAdjacencyList(pairs);

        // find the groups
        // visit each node then its children then their children etc,
        // populate map of visited ids along with group id.
        for (Map.Entry<Integer,Set<Integer>> entry: adjacencyList.entrySet()){
            if(!visitedAndGroupId.containsKey(entry.getKey())) {
                search(entry.getKey(), entry.getValue());
                groupId++;
            }
        }

        // build groups container
        final List<Group> groups = new ArrayList<>(groupId-1);
        for (int i = 0; i < groupId; i++) {
            groups.add(new Group(i));
        }

        // populate groups
        // each key is our original id and the associated value is the group it belongs to
        visitedAndGroupId.forEach((id,groupId)->groups.get(groupId).addItem(id));

        // print output
        System.out.print("{ ");
        groups.forEach(System.out::print);
        System.out.print("} ");
    }

    private static void search(int parent, Set<Integer> children) {
        if(!visitedAndGroupId.containsKey(parent)){
            visitedAndGroupId.put(parent, groupId);
            for (int c:children){
                search(c, adjacencyList.get(c));
            }
        }
    }

Building the adjacency list:

private static HashMap<Integer,Set<Integer>> buildAdjacencyList(List<String> vertexPairs) {

        // build adjacency list
        HashMap<Integer,Set<Integer>> adjacencyList = new HashMap<>();
        int group = -1;
        for(String s:vertexPairs){
            String[] pair = s.split(" ");
            int v1 = Integer.parseInt(pair[0]);
            int v2 = Integer.parseInt(pair[1]);

            if(!adjacencyList.containsKey(v1) && !adjacencyList.containsKey(v2)){
                // new pair
                adjacencyList.put(v1, new HashSet<>(Arrays.asList(v2)));
                adjacencyList.put(v2, new HashSet<>(Arrays.asList(v1)));
                continue;
            } else if (!adjacencyList.containsKey(v1) && adjacencyList.containsKey(v2)){
                // one vertex is new, one vertex exists
                addAndUpdate(v1,v2,adjacencyList);
                continue;
            } else if (adjacencyList.containsKey(v1) && !adjacencyList.containsKey(v2)){
                // one vertex is new, one vertex exists
                addAndUpdate(v2,v1,adjacencyList);
                continue;
            } else {
                // vertices already in hashset but this is a new edge between the two
                adjacencyList.get(v1).add(v2);
                adjacencyList.get(v2).add(v1);
            }
        }

        return adjacencyList;
    }

    private static void addAndUpdate(int newV, int existingV, HashMap<Integer, Set<Integer>> adjacencyList) {
        Set<Integer> t = adjacencyList.get(existingV);
        Set<Integer> newSet = new HashSet<>();
        newSet.add(existingV);
        adjacencyList.put(newV,newSet);
        t.add(newV);
    }

Here is the Group class: (getters/setters not used for brevity)

private static class Group {
        public int GroupId;
        public int Count=0;
        public List<Integer> Contents;

        public Group(int groupId) {
            GroupId = groupId;
            Contents = new ArrayList<>();
        }

        public void addItem(int n){
            Count++;
            Contents.add(n);
        }

        @Override
        public String toString() {
            return  " " + Count +
                    "=" + Contents+", ";
        }
    }

The output is: for input ("6 11", "9 5", "11 9", "15 9", "13 15", "12 14", "15 16", "1 16") is

{  8=[16, 1, 5, 6, 9, 11, 13, 15],  2=[12, 14], } 

and for input ("40 22","60 6","22 39","43 40","22 55","48 57","42 41","22 57","6 42","33 74","70 46","4 11","6 28","22 79","61 34","77 40","4 8","72 26","62 50","72 51","1 79","34 29","77 41","2 48","43 2","62 45","43 17","19 33","76 4","35 54") is

{  17=[1, 2, 6, 77, 79, 17, 22, 28, 39, 40, 41, 42, 43, 48, 55, 57, 60],  4=[4, 8, 11, 76],  2=[70, 46],  3=[72, 26, 51],  3=[74, 19, 33],  3=[29, 34, 61],  2=[35, 54],  3=[45, 50, 62], } 

Ok, a couple of observations.

• The order of the data appears to be important. If you move [6,11] right after [11,9] it works as you expect. In fact, I changed your input array to a List so I could shuffle it. Each time your output is substantially different than the previous iteration. This may offer a hint as to where the problem lies.

• I recommend you liberally sprinkle some print statements at key locations to do state checks as path to understand what it is doing.

• This has nothing to do with your problem but here is a sample of your code. You already have set so no need to get it again to add the value. Just use the set you already have.

Set<Integer> set = map.get(k);
 
if (set.contains(first)) {
        map.get(k).add(second);
        found = true;
        break;
}

It would also help others help you if you would do some explaining of how you expect this to work. Not everyone is fluent in graph theory.