0 1 2 3 4 5 6 7 8 9

10 components

9 0

0 1 2 3 4 5 6 7 8 0

9 components

3 4

0 1 2  4 5 6 7 8 0

8 components

5 8

0 1 2 4 4  6 7 8 0

7 components

7 2

0 1 2 4 4 8 6  8 0

6 components

2 1

0 1  4 4 8 6  8 0

5 components

5 7

0 1 1 4 4  6 1  0

4 components

0 3

 1 1 4 4 1 6 1 1

3 components

4 2

 1 1   1 6 1 1

2 components

    public static void main(String[] args) {

        //initialize N components

        int N = StdIn.readInt();

        UFQuickFind uf = new UFQuickFind(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");

                continue;

            }

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

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

            StdOut.println(uf);

        }

package com.qiusongde;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class UFQuickFind {

    private int[] id;//access to component id (site indexed)

    private int count;//number of components

    public UFQuickFind(int n) {

        //initialize count and id

        count = n;

        id = new int[n];

        for(int i = 0; i < n; i++) {

            id[i] = i;

        }

    }

    public int count() {

        return count;

    }

    public boolean connected(int p, int q) {

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

    }

    public int find(int p) {

        return id[p];

    }

    public void union(int p, int q) {

        int pID = find(p);

        int qID = find(q);

        //do nothing if p and q are already

        //in the same component

        if(pID == qID)

            return;

        //rename p's component to q's name

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

            if(id[i] == pID)

                id[i] = qID;

        }

        count--;

    }

    @Override

    public String toString() {

        String s = "";

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

            s += id[i] + " ";

        }

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

        return s;

    }

    public static void main(String[] args) {

        //initialize N components

        int N = StdIn.readInt();

        UFQuickFind uf = new UFQuickFind(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");

                continue;

            }

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

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

            StdOut.println(uf);

        }

    }

}