> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/10.-graph/589.connecting-graph.md).

# 589.Connecting Graph

1.Description(Medium)

Given`n`nodes in a graph labeled from`1`to`n`. 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 node`a`and 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**](https://www.lintcode.com/en/problem/connecting-graph/#tags)

[Union Find](https://www.lintcode.com/tag/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中每一个节点的组号(即它们所在树的根节点的序号)，

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

![](/files/-M33gmwAe9_RZdf1ijnC)

```
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);
        }
}
```