package UnionFind; import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List; public class UnionFindProblem { public static void main(String[] args) {
// TODO Auto-generated method stub }
/*
* 网上查了一下：http://blog.csdn.net/dm_vincent/article/details/7655764
* 这个人写的不错，但是他是抄袭这个普林斯顿的教授的视频：
* https://www.youtube.com/watch?v=H0bkmI1Xsxg&list=PLe-ggMe31CTexoNYnMhbHaWhQ0dvcy43t&index=2#t=379.668
* Union Find主要有两个部分，一个部分是Find Query，Check if two objects are in the same component.
* 另一个部分是Union Command,也就是replace components containing two objects with their union.
* 那么我们构建一个UF class
* public class UF
* UF(int N)------initialize with N object
* void union(int p,int q)--------add connection between p and q
* boolean connected(int p,int q)-------are p and q in the same component?
* 那么如何来构建Data Structure呢？
* Integer array id[] of size N and p and q are connected iff they have the same id.
* 0 1 2 3 4 5 6 7 8
* id[] 0 1 1 8 8 0 0 1 8 8表明0，5，6相连的
* 那么Find就只需要看id相不相等，然后Union就相对来说比较复杂
* To Merge components containing p and q, change all entries whose id equals id[p] to id[q].
* id[] 1 1 1 8 8 1 1 1 8 8 after union of 6 and 1
*/
public class QuickFindUF{
private int[] id;
public QuickFindUF(int N){
id=new int[N];
for(int i=0;i<N;i++)
id[i]=i;
}
public boolean connected(int p,int q){
return id[p]==id[q];
}
public void union(int p,int q){
int pid=id[p];
int qid=id[q];
for(int i=0;i<id.length;i++)
if(id[i]==pid)
id[i]=qid;
}
/*
* 那么我们能不能再把程序更进步一下吗？Quick-Union还是一样的ds，但是，这里id[i] is parent of i,
* Root of i is id[id[id[..id[i]..]]].Keep going until it doesn't change
* 0 1 2 3 4 5 6 7 8 9
* id[]0 1 9 4 9 6 6 7 8 9
* 0 1 9 6 7 8
* / \ |
* 2 4 5
* |
* 3
* 这里9，2，4，3在一起
* check if p and q have the same root
* Union to merge components containing p and q, set the id of p's root to the id of q's root
*/
public class QuickUnionUF2{
private int[] id;
public QuickUnionUF2(int N){
id=new int[N];
for(int i=0;i<N;i++)
id[i]=i;
}
private int root(int i){
while(i!=id[i])
i=id[i];//一直找到最高的父节点
return i;
}
public boolean connected(int p,int q){
return root(p)==root(q);
}
public void union(int p,int q){
int i=root(p);
int j=root(q);
id[i]=j;
}
}
}
/*
* 上面两种的比较，
* initialize union find defect
* quick-find N N 1 Union too expensive
* quick-union N N N Find too expensive,tree are too tall
* weightd QU N lgN lgN
* 我们会发现如果用quick union的话树会非常的长，所以我们不能固定模式的union（a，b）一定是把b加到a的子树，我们
* 应该看ab树的大小，把小的放在大的下面，这样可以节省一部分查找时间
*/
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
* 130. Surrounded Regions
* 2016-4-3 by Mingyang
* union 什么：所有从边界可达的O元素union在一起
* union 目的：union完成后那些没有在边界可达O集合中的O是需要翻转的
*/
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0)
return;
int rows = board.length, cols = board[0].length;
int oRoot = rows * cols;
initUnionFind(rows * cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'X') continue;
int curr = i * cols + j;
if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
union(curr, oRoot);
} else {
if (j + 1 < cols && board[i][j + 1] == 'O')
union(curr, i * cols + j + 1);
if (j - 1 >= 0 && board[i][j - 1] == 'O')
union(curr, i * cols + j - 1);
if (i + 1 < rows && board[i + 1][j] == 'O')
union(curr, (i + 1) * cols + j);
if (i - 1 >= 0 && board[i - 1][j] == 'O')
union(curr, (i - 1) * cols + j);
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O' && find(i * cols + j) != oRoot) {
board[i][j] = 'X';
}
}
}
}
int[] s;
int[] rank;
private void initUnionFind(int n) {
s = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i <= n; i++)
s[i] = i;
rank[n] = n + 1;
}
private int find(int p) {
if (s[p] == p) return p;
else return s[p] = find(s[p]);
}
private void union(int p, int q) {
int pRoot = find(p), qRoot = find(q);
if (pRoot == qRoot) return;
if (rank[pRoot] < rank[qRoot]) {//保证小的树在大的下面
s[pRoot] = qRoot;
} else {
if (rank[pRoot] == rank[qRoot])
rank[pRoot]++;
s[qRoot] = pRoot;
}
}
/*
* 200.Number of Islands
* 2016-4-3 by Mingyang
* union 什么：两个相邻的1元素
* union 目的：union后计数union集合数量（通过计数union数组中根节点数量）
*/
class UF {
public int count = 0;
public int[] id = null;
public UF(int m, int n, char[][] grid) {
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '1') count++;
}
}
id = new int[m * n];
for(int i = 0; i < m * n; i++) {
id[i] = i;
}
}
public int find(int p) {
while(p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}
public boolean isConnected(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot != qRoot) return false;
else return true;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}
public int numIslands(char[][] grid) {
if(grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
UF uf = new UF(m , n, grid);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '0') continue;
int p = i * n + j;
int q;
if(i > 0 && grid[i - 1][j] == '1') {
q = p - n;
uf.union(p, q);
}
if(i < m - 1 && grid[i + 1][j] == '1') {
q = p + n;
uf.union(p, q);
}
if(j > 0 && grid[i][j - 1] == '1') {
q = p - 1;
uf.union(p, q);
}
if(j < n - 1 && grid[i][j + 1] == '1') {
q = p + 1;
uf.union(p, q);
}
}
}
return uf.count;
}
//当然你也会觉得下面的可能更简单，那就是另外一种情况了，
//设一个叫count的值，没遇到一个1，就把所有相连的1全部变为0，这样，到底遇到几次1，就是最终有几个小岛啦
public int numIslands2(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
int count = 0; for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
public void dfs(char[][] grid, int i, int j) {
// validity checking
if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1)
return; // if current cell is water or visited
if (grid[i][j] != '1')
return; // set visited cell to '0'
grid[i][j] = '0'; // merge all adjacent land
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
/*
* 261.Graph Valid Tree
* 2016-4-3 by Mingyang
* 我们在Graph里面用其他方法做了一下这里我们再用并查集来做
* union 什么：一条边的两个顶点
* union 目的：若union两个顶点时发现根一样，说明已经在同一棵树中，
* 说明输入graph存在环，非tree；union结束后，计数有多少个不同的根，当且仅当存在一个根时事vaild tree
*/
public boolean validTree(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for(int i = 0; i < edges.length; i++){
// 如果两个节点已经在同一集合中，说明新的边将产生环路
if(!uf.union(edges[i][0], edges[i][1])){
return false;
}
}
return uf.count() == 1;
}
public class UnionFind {
int[] ids;
int cnt;
public UnionFind(int size){
this.ids = new int[size];
//初始化并查集，每个节点对应自己的集合号
for(int i = 0; i < this.ids.length; i++){
this.ids[i] = i;
}
this.cnt = size;
}
public boolean union(int m, int n){
int src = find(m);
int dst = find(n);
//如果两个节点不在同一集合中，将两个集合合并为一个
if(src != dst){
for(int i = 0; i < ids.length; i++){
if(ids[i] == src){
ids[i] = dst;
}
}
// 合并完集合后，集合数减一
cnt--;
return true;
} else {
return false;
}
}
public int find(int m){
return ids[m];
}
public int count(){
return cnt;
}
}
/*
* 305 Number of Islands II
* 2016-4-3 by Mingyang
* Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k ).
* Originally, the 2D matrix is all 0 which means there is only sea in the matrix.
* The list pair has k operator and each operator has two integer A[i].x, A[i].y means
* that you can change the grid matrix[A[i].x][A[i].y] from sea to island.
* Return how many island are there in the matrix after each operator.
*/
private int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
UnionFind2D islands = new UnionFind2D(m, n);
List<Integer> ans = new ArrayList<Integer>();
for (int[] position : positions) {
int x = position[0], y = position[1];
int p = islands.add(x, y);
for (int[] d : dir) {
int q = islands.getID(x + d[0], y + d[1]);
if (q > 0 && !islands.find(p, q))
islands.unite(p, q);
}
ans.add(islands.size());
}
return ans;
}
}
class UnionFind2D {
private int[] id;
private int[] sz;
private int m, n, count;
public UnionFind2D(int m, int n) {
this.count = 0;
this.n = n;
this.m = m;
this.id = new int[m * n + 1];
this.sz = new int[m * n + 1];
}
public int index(int x, int y) { return x * n + y + 1; }
public int size() { return this.count; }
public int getID(int x, int y) {
if (0 <= x && x < m && 0<= y && y < n)
return id[index(x, y)];
return 0;
}
public int add(int x, int y) {
int i = index(x, y);
id[i] = i; sz[i] = 1;
++count;
return i;
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
public void unite(int p, int q) {
int i = root(p), j = root(q);
if (sz[i] < sz[j]) { //weighted quick union
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
--count;
}
private int root(int i) {
for (;i != id[i]; i = id[i])
id[i] = id[id[i]]; //path compression
return i;
}
}