package question;


import java.util.*;

public class Question721 {
 public static void main(String[] args) {
 //[["David","David0@m.co","David1@m.co"],
 // ["David","David3@m.co","David4@m.co"],
 // ["David","David4@m.co","David5@m.co"],
 // ["David","David2@m.co","David3@m.co"],
 // ["David","David1@m.co","David2@m.co"]]
 List<String> list1 = new LinkedList<>();
 list1.add("David");
 list1.add("David0@m.co");
 list1.add("David1@m.co");
 List<String> list2 = new LinkedList<>();
 list2.add("David");
 list2.add("David3@m.co");
 list2.add("David4@m.co");
 List<String> list3 = new LinkedList<>();
 list3.add("David");
 list3.add("David4@m.co");
 list3.add("David5@m.co");
 List<String> list4 = new LinkedList<>();
 list4.add("David");
 list4.add("David2@m.co");
 list4.add("David3@m.co");
 List<String> list5 = new LinkedList<>();
 list5.add("David");
 list5.add("David1@m.co");
 list5.add("David2@m.co");
 List<List<String>> in = new LinkedList<>();
 in.add(list1);
 in.add(list2);
 in.add(list3);
 in.add(list4);
 in.add(list5);
 new Question721().accountsMerge(in);
 }

 public List<List<String>> accountsMerge(List<List<String>> accounts) {
 Map<String, Integer> indexMap = new HashMap<>();
 Map<String, String> nameMap = new HashMap<>();

 int index = 0;
 for (List<String> account : accounts) {
 String name = account.get(0);
 for (int i = 1; i < account.size(); i++) {
 String email = account.get(i);
 if (!indexMap.containsKey(email)) {
 indexMap.put(email, index++);
 nameMap.put(email, name);
 }
 }
 }

 UnionFind unionFind = new UnionFind(index);
 for (List<String> account : accounts) {
 String first = account.get(1);
 for (int i = 2; i < account.size(); i++) {
 String cur = account.get(i);
 unionFind.merge(indexMap.get(first), indexMap.get(cur));
 }
 }

 List<List<String>> res = new ArrayList<>();
 index=0;
 HashMap<Integer, Integer> findP = new HashMap<>();
 for (int i = 0; i < unionFind.p.length; i++) {
 if (unionFind.find(i)==i) {
 res.add(new LinkedList<>());
 findP.put(i, index++);
 }
 }

 for (Map.Entry<String, Integer> entry : indexMap.entrySet()) {
 res.get(findP.get(unionFind.find(entry.getValue()))).add(entry.getKey());
 }

 Comparator<String> comparator = new Comparator<String>() {
 @Override
 public int compare(String o1, String o2) {
 return o1.compareTo(o2);
 }
 };
 for (List<String> re : res) {
 re.sort(comparator);
 }
 List<List<String>> tmp = new ArrayList<>(res.size());
 for (List<String> re : res) {
 List<String> list = new LinkedList<>();
 list.add(nameMap.get(re.get(0)));
 list.addAll(re);
 tmp.add(list);
 }
 return tmp;
 }

 private class UnionFind {
 int[] p;

 public UnionFind(int n) {
 p=new int[n];
 for (int i = 0; i < p.length; i++) {
 p[i]=i;
 }
 }

 public boolean merge(int x, int y) {
 x=find(x);
 y=find(y);
 if (x==y) return true;
 p[y]=x;
 return false;
 }

 public int find(int x) {
 if (x==p[x]) return x;
 p[x]=find(p[x]);
 return p[x];
 }
 }

 public List<List<String>> accountsMerge2(List<List<String>> accounts) {
 List<String> names = new LinkedList<>();
 Map<String, List<String>> map = new HashMap<>();
 for (int i = 0; i < accounts.size(); i++) {
 List<String> list = accounts.get(i);
 String name = list.get(0);
 if (map.containsKey(name)) {
 List<String> stringList = map.get(name);
 LinkedList<String> tmp = new LinkedList<>();
 boolean tf = true;
 boolean[] fl = new boolean[list.size()];
 for (int j = 1; j < list.size(); j++) {
 String s = list.get(j);
 boolean f = true;
 for (int k = 1; k < stringList.size(); k++) {
 if (s.equals(stringList.get(k))) {
 f = false;
 tf = false;
 }
 }
 if (f) tmp.add(s);
 }
 if (!tf) {
 stringList.addAll(tmp);
 } else {
 tmp.addFirst(name);
 map.put(name + "$", tmp);
 }
 } else {
 map.put(name, list);
 }
 }
 List<List<String>> res = new LinkedList<>();
 for (List<String> value : map.values()) {
 String name = value.get(0);
 value.sort((o1, o2) -> {
 if (o1.equals(name)) return -1;
 if (o2.equals(name)) return 1;
 return o1.compareTo(o2);
 });
 for (int i = 2; i < value.size(); ) {
 if (value.get(i).equals(value.get(i - 1))) {
 value.remove(i - 1);
 } else i++;
 }
 res.add(value);
 }
 return res;
 }
}