Union & Find

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int n;
	static int m;		
	static int answer;
	
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		Main M = new Main();
		n = 8;//;in.nextInt();
		unf =new int [n+1];
		for (int i = 0 ; i <= n ; i++) {
			unf[i] = i;
		}
		/*
		union(1,2);
		union(2,3);
		union(3,4);
		union(4,5);
		union(6,8);
		*/
		
		union(2,1);
		union(3,2);
		union(3,4);
		union(5,4);
		union(8,6);
		
		System.out.println("dump unf");
		for ( int x : unf)
			System.out.print(x+" ");
		System.out.println();
		
		find(1);
		
		find(2);
		
		System.out.println("after find");
		System.out.println("dump unf");
		for ( int x : unf)
			System.out.print(x+" ");
		System.out.println();
		
		
		for (int i = 0 ; i < 5; i++) {
			int fa = find(i);
			int fb = find(i+1);
			if(fa==fb)
				System.out.println(String.format("[%d %d] is union", i, i+1));
			else
				System.out.println(String.format("[%d %d] is non-union", i, i+1));
		}
	
	}
	static int []unf;
	private static int find(int v) {
		if(v == unf[v])
			return unf[v];
		else
			return unf[v]=find(unf[v]);
	}
	
	private static void union(int a, int b) {
		int fa = find(a);
		int fb = find(b);
		if(fa!=fb) 
			unf[fa] = fb;
		
	}

}


output
dump unf
0 4 1 1 4 4 6 7 6 
after find
dump unf
0 4 1 1 4 4 6 7 6 
[0 1] is non-union
[1 2] is union
[2 3] is union
[3 4] is union
[4 5] is union

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer;

	static int[] unf;
	public static int Find(int v) {
		if (v == unf[v]) return v;
		else return unf[v]=Find(unf[v]);
	}
	
	public static void Union ( int a , int b) {
		int fa = Find(a);
		int fb = Find(b);
		if( fa != fb)  unf[fa]=fb;		
	}
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		
		unf = new int [n+1];
		
		//start from 1
		for (int i = 1 ; i <= n ; i++ ) unf[i] = i;
		for (int i =1 ;  i<=m; i++) {
				int a = in.nextInt();
				int b = in.nextInt();
				Union(a, b);
		}
		
		int a = in.nextInt();
		int b = in.nextInt();
		int fa = Find(a);
		int fb = Find(b);

		if( fa == fb) System.out.println("YES");
		else System.out.println("NO");
		

	}


}

ex)
input
9 7
1 2
2 3
3 4
1 5
6 7
7 8
8 9
3 8
output
No

 

union : element를 bind시키는 역할

 

find : chain의 최상단 element를 찾아오며 호출된 v의 unf까지 링크를 생성.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int n;
	static int m;		
	static int answer;
	
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		Main M = new Main();
		n = 8;//;in.nextInt();
		unf =new int [n+1];
		for (int i = 0 ; i <= n ; i++) {
			unf[i] = i;
		}
		
		union(1,2);
		union(2,3);
		union(3,4);
		union(4,5);
		union(6,8);
		
		System.out.println("dump unf");
		for ( int x : unf)
			System.out.print(x+" ");
		System.out.println();
		
		find(1);
		
		find(2);
		
		System.out.println("after find");
		System.out.println("dump unf");
		for ( int x : unf)
			System.out.print(x+" ");
		System.out.println();
	
	}
	static int []unf;
	private static int find(int v) {
		if(v == unf[v])
			return unf[v];
		else
			return unf[v]=find(unf[v]);
	}
	
	private static void union(int a, int b) {
		int fa = find(a);
		int fb = find(b);
		if(fa!=fb) 
			unf[fa] = fb;
		
	}

}


output
dump unf
0 2 3 4 5 5 8 7 8 
after find
dump unf
0 2 5 5 5 5 8 7 8