ThirtyDays's blog

Almost Union-Find problem solution, HELP
By ThirtyDays, history, 4 years ago, In English

Problem link In this all first and third operation is the same as DSU. But in the second operation move(a, b) we have to move element 'a' to group containing b.

My approach: Instead of changing parent structure, I am using a different a vector parent2 for updating parent of element in move operation.

Code. Code . Correct code

I am getting the wrong answer.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem link doesn't open

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This can be done by maintaining which number belongs to which dis-joint set. You can use sets to maintain this which could give you O(1) operation for second operation. Whenever you would try to combine 2 disjoint sets, you would merge the smaller one into the bigger one. This would ensure you don't have O(n^2) operations.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate on the "You can use sets to maintain this which could give you O(1) operation for second operation" part a little more ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not good with markup that is used in codeforces (or anywhere else). So I am going the attach a piece of code in this comment which is a O(nlogn) implementation of DSU. This implementation uses LinkedList (can use vector in c++) to store which number belongs to which disjoint set. Instead of that, you can use a hashset to store this information. With this and some additional changes, you can easily implement the second operation. I'll leave the implementation to you.


      import java.util.ArrayList;
import java.util.LinkedList;

class UnionFind {

    private int noOfComponents, n;
    private int component[], size[];
    private ArrayList<LinkedList<Integer>> members;

    public UnionFind(int p) {
        n = p;
        noOfComponents = n;
        component = new int[n + 1];
        size = new int[n + 1];
        members = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            component[i] = i;
            size[i] = 1;
            members.add(new LinkedList<Integer>());
            members.get(i).add(i);
        }
    }

    public int find(int k) {
        return component[k];
    }

    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        if (size[a] > size[b]) {
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
        }
        LinkedList<Integer> membersofa = members.get(a);
        LinkedList<Integer> membersofb = members.get(b);
        for (int i = 0; i < size[a]; i++) {
            int member = membersofa.removeFirst();
            component[member] = component[b];
            membersofb.add(member);
        }
        size[b] = size[b] + size[a];
        noOfComponents--;
    }

    public int noOfComponents() {
        return noOfComponents;
    }
}
      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, I was doing a small mistake in taking input. First time I saw input terminate by using END Of the File(EOF). My code was working fine for one testcase. Now it's working.

→ Reply