fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11.     /**
  12.      * Merge usernames that belong to the same person based on shared emails using optimized DFS.
  13.      * 
  14.      * @param accounts A map where keys are usernames and values are lists of emails
  15.      * @return A list of lists, where each inner list contains usernames that belong to the same person
  16.      */
  17.     public static List<List<String>> mergeUsernames(Map<String, List<String>> accounts) {
  18.         // Step 1: Create email to username mappings
  19.         Map<String, Set<String>> emailToUsernames = new HashMap<>();
  20.  
  21.         // For each username, add it to the sets of all its emails
  22.         for (Map.Entry<String, List<String>> entry : accounts.entrySet()) {
  23.             String username = entry.getKey();
  24.             List<String> emails = entry.getValue();
  25.  
  26.             for (String email : emails) {
  27.                 if (!emailToUsernames.containsKey(email)) {
  28.                     emailToUsernames.put(email, new HashSet<>());
  29.                 }
  30.                 emailToUsernames.get(email).add(username);
  31.             }
  32.         }
  33.  
  34.         // Step 2: Build the graph where usernames are nodes
  35.         Map<String, Set<String>> graph = new HashMap<>();
  36.  
  37.         // Initialize graph with empty adjacency lists
  38.         for (String username : accounts.keySet()) {
  39.             graph.put(username, new HashSet<>());
  40.         }
  41.  
  42.         // For each email, connect all usernames that share it
  43.         for (Set<String> usernamesWithEmail : emailToUsernames.values()) {
  44.             if (usernamesWithEmail.size() > 1) {
  45.                 // Convert set to list for easier iteration
  46.                 List<String> usernamesList = new ArrayList<>(usernamesWithEmail);
  47.  
  48.                 // Connect each username with the first one (instead of all-to-all)
  49.                 // This reduces edge creation from O(k²) to O(k) per email
  50.                 String firstUsername = usernamesList.get(0);
  51.                 for (int i = 1; i < usernamesList.size(); i++) {
  52.                     String otherUsername = usernamesList.get(i);
  53.                     graph.get(firstUsername).add(otherUsername);
  54.                     graph.get(otherUsername).add(firstUsername);
  55.                 }
  56.             }
  57.         }
  58.  
  59.         // Step 3: Perform DFS to find connected components
  60.         Set<String> visited = new HashSet<>();
  61.         List<List<String>> result = new ArrayList<>();
  62.  
  63.         for (String username : accounts.keySet()) {
  64.             if (!visited.contains(username)) {
  65.                 List<String> connectedUsernames = new ArrayList<>();
  66.                 dfs(graph, username, visited, connectedUsernames);
  67.                 result.add(connectedUsernames);
  68.             }
  69.         }
  70.  
  71.         return result;
  72.     }
  73.  
  74.     /**
  75.      * Perform DFS to find all connected usernames.
  76.      */
  77.     private static void dfs(Map<String, Set<String>> graph, String username, 
  78.                            Set<String> visited, List<String> component) {
  79.         visited.add(username);
  80.         component.add(username);
  81.  
  82.         for (String neighbor : graph.get(username)) {
  83.             if (!visited.contains(neighbor)) {
  84.                 dfs(graph, neighbor, visited, component);
  85.             }
  86.         }
  87.     }
  88.  
  89.     // Example usage
  90.     public static void main(String[] args) {
  91.         Map<String, List<String>> accounts = new HashMap<>();
  92.         accounts.put("john", Arrays.asList("john@gmail.com", "john@yahoo.com"));
  93.         accounts.put("jane", Arrays.asList("jane@gmail.com"));
  94.         accounts.put("john2", Arrays.asList("john@gmail.com"));
  95.         accounts.put("mary", Arrays.asList("mary@hotmail.com"));
  96.         accounts.put("jane2", Arrays.asList("jane@gmail.com", "jane@yahoo.com"));
  97.         accounts.put("tom", Arrays.asList("tom@gmail.com"));
  98.         accounts.put("susan", Arrays.asList("susan@outlook.com"));
  99.         accounts.put("tom2", Arrays.asList("tom@gmail.com", "thomas@work.com"));
  100.  
  101.         List<List<String>> result = mergeUsernames(accounts);
  102.         System.out.println(result);
  103.     }
  104.  
  105. }
Success #stdin #stdout 0.08s 52308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[tom, tom2], [susan], [jane2, jane], [mary], [john, john2]]
https://ideone.com/tTAuVT
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!