589.Connecting Graph

1.Description(Medium)

Givennnodes in a graph labeled from1ton. There is no edges in the graph at beginning.

You need to support the following method: 1.connect(a, b), add an edge to connect nodeaand node b. 2.query(a, b)`, check if two nodes are connected

Example

5 // n = 5
query(1, 2) return false
connect(1, 2)
query(1, 3) return false
connect(2, 4)
query(1, 4) return true

Tags

Union Find

2.Code

public class ConnectingGraph { 

    public ConnectingGraph(int n) {
        // initialize your data structure here.
    }

    public void connect(int a, int b) {
        // Write your code here
    }

    public boolean  query(int a, int b) {
        // Write your code here
    }
}

经典的实现union find

http://blog.csdn.net/dm_vincent/article/details/7655764

可以采用parent-link的方式将节点组织起来，举例而言，id[p]的值就是p节点的父节点的序号，

如果p是树根的话，id[p]的值就是p，因此最后经过若干次查找，一个节点总是能够找到它的根节点，即满足id[root] = root的节点也就是组的根节点了，

然后就可以使用根节点的序号来表示组号。

所以在处理一个pair的时候，将首先找到pair中每一个节点的组号(即它们所在树的根节点的序号)，

如果属于不同的组的话，就将其中一个根节点的父节点设置为另外一个根节点，相当于将一颗独立的树编程另一颗独立的树的子树。

public class Solution_589 {

        private int[] father=null;

        public Solution_589(int n) {
            father=new int[n+1];
            for(int i=1;i<n+1;i++){
                father[i]=i;
            }
        }


        //寻找p的父节点，即根结点
        public int find(int p){
            while(p!=father[p]){
                p=father[father[p]];
            }
            return p;
        }

        public void connect(int a, int b) {
            int aRoot=find(a);
            int bRoot=find(b);
            //根结点相同，说明连通
            if(aRoot==bRoot) return;
            //否则，把一个根结点当做另一个的子树
            father[aRoot]=bRoot;        
        }

        //看根结点是否相同   
        public boolean  query(int a, int b) {
            return find(a)==find(b);
        }
}