package com.qiusongde;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class UFWQuickUnionPathCom {

    private int[] id;//parent link(site indexed)

    private int[] treesize;//size of component for roots(site indexed)

    private int count;//number of components

    public UFWQuickUnionPathCom(int N) {

        count = N;

        id = new int[N];

        for(int i = 0; i < N; i++)

            id[i] = i;

        treesize = new int[N];

        for(int i = 0; i < N; i++)

            treesize[i] = 1;

    }

    public int count() {

        return count;

    }

    public boolean connected(int p, int q) {

        return find(p) == find(q);

    }

    public int find(int p) {

        int root = p;//initialize root

        //find root(id[p] save the parent of p)

        while(root != id[root])

            root = id[root];

        //link every site from p to root to root

        while(id[p] != root) {//parent isn't root

            int nextp = id[p];

            id[p] = root;//link directly to root

            p = nextp;

        }

        return root;

    }

    public void union(int p, int q) {

        int pRoot = find(p);

        int qRoot = find(q);

        if(pRoot == qRoot)

            return;

        //make smaller root point to larger one

        if(treesize[pRoot] < treesize[qRoot]) {

            id[pRoot] = qRoot;

            treesize[qRoot] += treesize[pRoot];

        } else {

            id[qRoot] = pRoot;

            treesize[pRoot] += treesize[qRoot];

        }

        count--;

    }

    @Override

    public String toString() {

        String s = "";

        for(int i = 0; i < id.length; i++) {

            s += id[i] + " ";

        }

        s += "\n";

        for(int i = 0; i < treesize.length; i++) {

            s += treesize[i] + " ";

        }

        s += "\n" + count + " components";

        return s;

    }

    public static void main(String[] args) {

        //initialize N components

        int N = StdIn.readInt();

        UFWQuickUnionPathCom uf = new UFWQuickUnionPathCom(N);

        StdOut.println(uf);

        while(!StdIn.isEmpty()) {

            int p = StdIn.readInt();

            int q = StdIn.readInt();

            if(uf.connected(p, q)) {//ignore if connected

                StdOut.println(p + " " + q + " is connected");

                StdOut.println(uf);

                continue;

            }

            uf.union(p, q);//connect p and q

            StdOut.println(p + " " + q);

            StdOut.println(uf);

        }

    }

}

0 1 2 3 4 5 6 7 8 9

1 1 1 1 1 1 1 1 1 1

10 components

4 3

0 1 2 4 4 5 6 7 8 9

1 1 1 1 2 1 1 1 1 1

9 components

3 8

0 1 2 4 4 5 6 7 4 9

1 1 1 1 3 1 1 1 1 1

8 components

6 5

0 1 2 4 4 6 6 7 4 9

1 1 1 1 3 1 2 1 1 1

7 components

9 4

0 1 2 4 4 6 6 7 4 4

1 1 1 1 4 1 2 1 1 1

6 components

2 1

0 2 2 4 4 6 6 7 4 4

1 1 2 1 4 1 2 1 1 1

5 components

8 9 is connected

0 2 2 4 4 6 6 7 4 4

1 1 2 1 4 1 2 1 1 1

5 components

5 0

6 2 2 4 4 6 6 7 4 4

1 1 2 1 4 1 3 1 1 1

4 components

7 2

6 2 2 4 4 6 6 2 4 4

1 1 3 1 4 1 3 1 1 1

3 components

6 1

6 2 6 4 4 6 6 2 4 4

1 1 3 1 4 1 6 1 1 1

2 components

1 0 is connected

6 6 6 4 4 6 6 2 4 4

1 1 3 1 4 1 6 1 1 1

2 components

6 7 is connected

6 6 6 4 4 6 6 6 4 4

1 1 3 1 4 1 6 1 1 1

2 components