SHARE
TWEET

Untitled

a guest Dec 14th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  public static void main(String args[])
  5.   {
  6.     List<String> input = new ArrayList<>();
  7.     input.add("A,B,");
  8.     input.add("A,B,C");
  9.     input.add("D,,F");
  10.     input.add(",B,C");
  11.     input.add("D,E,F");
  12.     List<List<Integer>> res = matchRecords(input);
  13.     for (int i = 0; i < res.size(); i++) {
  14.       for (int j = 0; j < res.size(); j++) {
  15.         System.out.print(res.get(i).get(j) + " ");
  16.       }
  17.       System.out.println();
  18.     }
  19.   }
  20.  
  21.  public static List<List<Integer>> matchRecords(List<String> input) {
  22.    List<String[]> inputs = new ArrayList<>();
  23.    for (String p : input){
  24.      String[] s = p.split(",", -1);
  25.      inputs.add(s);
  26.    }
  27.  
  28.    UnionFind uf = new UnionFind(inputs.size());
  29.    for (int i = 0; i < inputs.size(); i++) {
  30.      for (int j = i + 1; j < inputs.size(); j++) {
  31.        if (match(inputs.get(i), inputs.get(j))) {
  32.          uf.union(i, j);
  33.        }
  34.      }
  35.    }
  36.  
  37.    List<List<Integer>> res = new ArrayList<>();
  38.    for (int i = 0; i < inputs.size(); i++) {
  39.      List<Integer> next = new ArrayList<>();
  40.      for (int j = 0; j < inputs.size(); j++) {
  41.        if (i == j || uf.find(i) == uf.find(j)) {
  42.          next.add(1);
  43.        } else {
  44.          next.add(0);
  45.        }
  46.      }
  47.      res.add(next);
  48.    }
  49.  
  50.    return res;
  51.  }
  52.  
  53.  public static boolean match(String[] s1, String[] s2) {
  54.    for (int i = 0; i < s1.length; i++) {
  55.      if (s1[i].length() > 0 && s1[i].equals(s2[i])) {
  56.        return true;
  57.      }
  58.    }
  59.  
  60.    return false;
  61.  }
  62.  
  63.  private static class UnionFind {
  64.  
  65.         private int[] parent;
  66.         private int   components;
  67.         private int[] size;
  68.  
  69.         UnionFind(int n) {
  70.             parent = new int[n];
  71.             size = new int[n];
  72.             components = n;
  73.  
  74.             for (int i = 0; i < n; i++) {
  75.                 parent[i] = i;
  76.                         size[i] = 1;
  77.             }
  78.         }
  79.  
  80.         void union(int p, int q) {
  81.             int parentP = find(p);
  82.             int parentQ = find(q);
  83.  
  84.             if (parentP == parentQ) {
  85.                 return;
  86.             }
  87.            
  88.             if (size[parentP] < size[parentQ]) {
  89.                 parent[parentP] = parentQ;
  90.                 size[parentQ] += size[parentP];
  91.             } else {
  92.                 parent[parentQ] = parentP;
  93.                 size[parentP] += size[parentQ];
  94.             }
  95.            
  96.             components--;
  97.         }
  98.  
  99.         int find(int p) {
  100.             while (p != parent[p]) {
  101.                 p = parent[p];
  102.             }
  103.             return p;
  104.         }
  105.  
  106.         int getComponents() {
  107.             return components;
  108.         }
  109.     }
  110.  
  111. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top