Contacts Detective

Given a list of contact information，
Each contact has name, phone and email. 
Contacts with same email are same person,
Contacts with same phone are also same person, 
each person may have multiple names, phones or emails.  
Task: Group contacts by person

public class Main {
    static public class Contact {
        public Contact(String name, String phone, String email) {
            this.name = name;
            this.phone = phone;
            this.email = email;
        }
        public String name;
        public String phone;
        public String email;

        @Override
        public int hashCode() {
            return phone.hashCode() ^ email.hashCode();
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (other == null || ! (other instanceof Contact)) {
                return false;
            }

            Contact o = (Contact) other;
            return this.phone == o.phone && this.email == o.email;
        }
    }

    static Set> merge(List input) {
        Map> map = new HashMap<>();
        Set> output = new HashSet<>();
        for (Contact contact: input) {
            Set sameContacts = new HashSet<>();
            Set differentEmails = new HashSet<>();
            Set differentPhones = new HashSet<>();

            sameContacts.add(contact);
            differentEmails.add(contact.email);
            differentPhones.add(contact.phone);

            if (map.containsKey(contact.phone)) {
                Set dupContacts = map.get(contact.phone);
                sameContacts.addAll(dupContacts);
                for (Contact c: dupContacts) {
                    differentEmails.add(c.email);
                    differentPhones.add(c.phone);
                }
            }

            if (map.containsKey(contact.email)) {
                Set dupContacts = map.get(contact.email);
                sameContacts.addAll(dupContacts);
                for (Contact c: dupContacts) {
                    differentEmails.add(c.email);
                    differentPhones.add(c.phone);
                }
            }

            // Make all phone keys point to the same set
            for(String phone: differentPhones) {
                map.put(phone, sameContacts);
            }

            // Make all email keys point to the same set
            for(String email: differentEmails) {
                map.put(email, sameContacts);
            }
        }

        output.addAll(map.values());
        return output;
    }

    static Set> merge2(List input) {
        Map> map = new HashMap<>();
        for (Contact contact: input) {
            if (map.containsKey(contact.phone)) {
                map.get(contact.phone).add(contact);
            } else {
                Set contacts = new HashSet<>();
                contacts.add(contact);
                map.put(contact.phone, contacts);
            }

            if (map.containsKey(contact.email)) {
                map.get(contact.email).add(contact);
            } else {
                Set contacts = new HashSet<>();
                contacts.add(contact);
                map.put(contact.email, contacts);
            }
        }

        Set> output = new HashSet<>();
        Set visited =  new HashSet<>();
        for (Contact contact: input) {
            if (!visited.contains(contact)) {
                Set sameContacts = new HashSet<>();
                getSameContacts(map, contact, sameContacts, visited);
                output.add(sameContacts);
            }
        }
       return output;
    }

    static void getSameContacts(Map> map, Contact contact, Set sameContacts,  Set visited) {
          if (!visited.contains(contact)) {
              sameContacts.add(contact);
              visited.add(contact);
              if (map.containsKey(contact.phone)) {
                  Set contactsSamePonne = map.get(contact.phone);
                  for (Contact c : contactsSamePonne) {
                      getSameContacts(map, c, sameContacts, visited);
                  }
              }
              if (map.containsKey(contact.email)) {
                  Set contactsSameEmail = map.get(contact.email);
                  for (Contact c : contactsSameEmail) {
                      getSameContacts(map, c, sameContacts, visited);
                  }
              }
          }
    }

    public static void main(String[] args) throws InterruptedException {
        List contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone3", "email3")
        );

        Set> out =  merge(contacts);
        Assert.isTrue(out.size() == 3);

        contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone3", "email3"),
            new Contact("name4", "phone1", "email2")
        );
        out =  merge(contacts);
        Assert.isTrue(out.size() == 2);

       contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone1", "email3"),
            new Contact("name123", "phone123", "email123"),
            new Contact("name4", "phone2", "email1")
        );
        out =  merge(contacts);
        Assert.isTrue(out.size() == 2);

        contacts = Arrays.asList(
            new Contact("name1", "phone1", "email1"),
            new Contact("name2", "phone2", "email2"),
            new Contact("name3", "phone1", "email3"),
            new Contact("name123", "phone123", "email123"),
            new Contact("name4", "phone5", "email2")
        );
        out =  merge(contacts);
        Assert.isTrue(out.size() == 3);
    }
 }

Class ContactGroup
{
      Public List<Contact> contact;
      Public Hashset<string> phone;

      Public ContactGroup()
      {
          contact= new List<Contact>();
          Phone = new HashSet<string>();
       }
}


List<List<Contact>> GroupContact(List<Contact> contacts)
{
 if(contacts == null) return null;
 
 Dictionary<string, ContactGroup>> contactDictionary = new Dictionary<string, ContactGroup>();

 foreach(Contact contact in contacts)
 {
    if(!contactDictionary.ContainsKey(contact.email))
    {
       contactDictionary[contact.email] = new ContactGroup();
    }
  
    contactDictionary[contact.email].Contact.Add(contact);
    contactDictionary[contact.email].Phone.Add(contact.phone);
 }
 
 List<ContactGroup> res = new List<ContactGroup>();
 foreach(var kvp in contactDictionary)
 {
      Bool bFound = false;
      foreach(var contactGroup in res)
      {
        if(contactGroup.phone.IntersetWith(kvp.phone).Any())
        {
            contactGroup.contact.Add(kvp.value.contact);
            contactGroup.Phone.Add(kvp.value.Phone);
            bFound = true;
            break;
         }
      }
      if(!bFound)
      {
          res.Add(kvp.value);
      }

   }

   List<List<Contact>> resContact = new List<List<Contact>>();
   foreach(ContactGroup group in res)
   {
      resContact.Add(group.contact);
   }
   return resContact;
}

static Set<Set<Contact>> merge5(List<Contact> contacts) {
        Map<String, String> map = new HashMap<>();
        for (Contact c : contacts) {
            map.put(c.email, c.email);
            map.put(c.phone, c.phone);
        }

        for (Contact c : contacts) {
            union(map, c.phone, c.email);
        }

        Map<String, Set<Contact>> temp = new HashMap<>();
        for (Contact c : contacts) {
            String key = find(map, c.email);
            temp.computeIfAbsent(key, x -> new HashSet<>()).add(c);
        }
        Set<Set<Contact>> output = new HashSet<>();
        for (Map.Entry<String, Set<Contact>> entry : temp.entrySet()) {
            if (!entry.getValue().isEmpty()) {
                output.add(entry.getValue());
            }
        }
        return output;
    }

    static void union(Map<String, String> map, String key1, String key2) {
        map.put(find(map, key1), find(map, key2));
    }

    static String find(Map<String, String> map, String key) {
        if (key != map.get(key)) {
            map.put(key, find(map, map.get(key)));
        }
        return map.get(key);
    }