学习内容

LeeCodeJava

1579.保证图可完全遍历

我的代码:

  1. class Solution {
  2.     public int maxNumEdgesToRemove(int n, int[][] edges) {
  3.         UnionFind origin=new UnionFind(new int[n]);
  4.         for (int i = 0; i < n; i++) {
  5.             origin.data[i]=i;
  6.         }
  7.         int count=0;
  8.         ArrayList<Integer> bob=new ArrayList<>();
  9.         ArrayList<Integer> alice=new ArrayList<>();
  10.         for (int i = 0; i < edges.length; i++) {
  11.             switch (edges[i][0]){
  12.                 case 3:
  13.                     if(!origin.union(edges[i][1]-1,edges[i][2]-1)){
  14.                         count++;
  15.                     }
  16.                     break;
  17.                 case 1:
  18.                     alice.add(i);
  19.                     break;
  20.                 case 2:
  21.                     bob.add(i);
  22.                     break;
  23.                 default:
  24.                     System.out.println("error");
  25.                     break;
  26.             }
  27.         }
  28.         UnionFind uBob=new UnionFind(Arrays.copyOfRange(origin.data,0,origin.data.length));
  29.         UnionFind uAlice=new UnionFind(Arrays.copyOfRange(origin.data,0,origin.data.length));
  30.         for(Integer index:bob){
  31.             if(!uBob.union(edges[index][1]-1,edges[index][2]-1)){
  32.                 count++;
  33.             }
  34.         }
  35.         for(Integer index:alice){
  36.             if(!uAlice.union(edges[index][1]-1,edges[index][2]-1)){
  37.                 count++;
  38.             }
  39.         }
  40.         if(uAlice.isConnected()&&uBob.isConnected()){
  41.             return count;
  42.         }else{
  43.             return -1;
  44.         }
  45.     }
  46. }
  47. class UnionFind{
  48.     int[] data;
  50.     public UnionFind(int[] data) {
  51.         this.data = data;
  52.     }
  54.     public Boolean union(int a,int b){
  55.         int fa=find(a);
  56.         int fb=find(b);
  57.         if(fa!=fb){
  58.             data[fb]=fa;
  59.             return true;
  60.         }else{
  61.             return false;
  62.         }
  63.     }
  65.     public int find(int a){
  66.         if(data[a]==a){
  67.             return a;
  68.         }else{
  69.             return find(data[a]);
  70.         }
  71.     }
  73.     public boolean isConnected(){
  74.         int temp=0;
  75.         for (int i = 0; i < data.length; i++) {
  76.             if(data[i]==i){
  77.                 temp++;
  78.             }
  79.         }
  80.         return temp <= 1;
  81.     }
  82. }

思路:

这是一个相当标准的并查集问题,使用三个并查集来分别代表三个集合,优先计算基础的连接,随后计算两个集合独有的连接,最后使用并查集的标准版方法来解决问题.

注意:

1.指向同一个对象的类,其的不同实例之间会通过这个对象来联系起来,换句话说,类中的对象在一个新的类中并不会被复制一个新,而是直接使用老的.

改进思路:

改进判断其是否连通的方法,减少其遍历的次数.
使用带有优化的并查集模板来减少计算次数,防止长串.
减少使用ArrayList,来减少计算时间,如果想要使用ArrayList,作为缓存,还不如直接使用数组来遍历,内存的分配才比较花费时间.

优解代码

主函数:

  1. class Solution {
  2.     public int maxNumEdgesToRemove(int n, int[][] edges) {
  3.         UnionFind ufa = new UnionFind(n);
  4.         UnionFind ufb = new UnionFind(n);
  5.         //无用边的数量
  6.         int count = 0;
  8.         // 节点编号改为从 0 开始
  9.         for (int[] edge : edges) {
  10.             --edge[1];
  11.             --edge[2];
  12.         }
  14.         // 公共边
  15.         for (int[] edge : edges) {
  16.             if (edge[0] == 3) {
  17.                 if (!ufa.unite(edge[1], edge[2])) {
  18.                     ++count;
  19.                 } else {
  20.                     ufb.unite(edge[1], edge[2]);
  21.                 }
  22.             }
  23.         }
  25.         // 独占边
  26.         for (int[] edge : edges) {
  27.             if (edge[0] == 1) {
  28.                 // Alice 独占边
  29.                 if (!ufa.unite(edge[1], edge[2])) {
  30.                     ++count;
  31.                 }
  32.             } else if (edge[0] == 2) {
  33.                 // Bob 独占边
  34.                 if (!ufb.unite(edge[1], edge[2])) {
  35.                     ++count;
  36.                 }
  37.             }
  38.         }
  40.         if (ufa.setCount != 1 || ufb.setCount != 1) {
  41.             return -1;
  42.         }
  43.         return count;
  44.     }
  45. }

并查集模板:

  1. class UnionFind {
  2.     int[] parent;
  3.     int[] size;
  4.     int n;
  5.     int setCount;
  7.     public UnionFind(int n) {
  8.         this.n = n;
  9.         this.setCount = n;//未被改变的节点数目
  10.         this.parent = new int[n];
  11.         this.size = new int[n];
  12.         Arrays.fill(size, 1);//初值设定为1,作为每个串的初始长度:1
  13.         for (int i = 0; i < n; ++i) {
  14.             parent[i] = i;//标记值为1
  15.         }
  16.     }
  18.     public int findSet(int x) {
  19.         return parent[x] == x ? x : (parent[x] = findSet(parent[x]));
  20.         //使用递归找根
  21.     }
  23.     public boolean unite(int x, int y) {
  24.         x = findSet(x);
  25.         y = findSet(y);
  26.         if (x == y) {
  27.             return false;
  28.         }
  29.         //如果两个根值的size不同的话,宁可让长的接在短的后面,也不要让短的接在长的后面
  30.         if (size[x] < size[y]) {
  31.             int temp = x;
  32.             x = y;
  33.             y = temp;
  34.         }
  35.         //y:短 x:长
  36.         parent[y] = x;
  37.         //短的那部分的size,加上长的那部分的size,成为新的size
  38.         size[x] += size[y];
  39.         //每次成功的连接都会让未被改变根的节点少一个,当这个值降为1时,全部连接.
  40.         --setCount;
  41.         return true;
  42.     }
  44.     //判断两个节点是否连接
  45.     public boolean connected(int x, int y) {
  46.         x = findSet(x);
  47.         y = findSet(y);
  48.         return x == y;
  49.     }
  51.     public boolean allConnected(){
  52.         return setCount==1;
  53.     }
  54. }

心得:

1.思路的差距不大,主要的差距是没有很好的利用并查集的模板,导致了主函数变得臃肿与不优雅,需要对于并查集的模板进行深入研究.
2.—a 比 a— 快