https://leetcode.com/problems/accounts-merge/discuss/109158/Java-Solution-(Build-graph-+-DFS-search)

 

1 class Solution { 2     public List
     
      
       > accountsMerge(List
       
        
         > accounts) { 3         List
         
          
           > res = new ArrayList<>(); 4 if(accounts == null) return res; 5 HashMap
           
             map = new HashMap<>(); 6 HashMap
            
             > graph = new HashMap<>(); 7 for(int j = 0; j < accounts.size(); j++){ 8 List
             
               account = accounts.get(j); 9 String name = account.get(0);10 for(int i = 1; i < account.size(); i++){11 if(!graph.containsKey(account.get(i))){12 graph.put(account.get(i), new HashSet<>());13 }14 map.put(account.get(i), name);15 16 if(i != 1){17 graph.get(account.get(i)).add(account.get(i-1));18 graph.get(account.get(i-1)).add(account.get(i));19 }20 }21 }22 23 Set
              
                visited = new HashSet<>();24 for(String email : map.keySet()){25 List
               
                 list = new ArrayList<>();26 String name = map.get(email);27 if(!visited.contains(email)){ //判断是否visited之后， 没有的话要加进去28 visited.add(email);29 dfs(graph, visited, list, email);30 Collections.sort(list);31 list.add(0, name);32 res.add(list);33 } 34 }35 return res; 36 }37 38 public void dfs(HashMap
                
                 > graph, Set
                 
                   visited, List
                  
                    list, String email){39 list.add(email);40 for(String neighbor : graph.get(email)){41 if(!visited.contains(neighbor)){42 visited.add(neighbor);43 dfs(graph, visited, list, neighbor);44 }45 }46 }47 }