并查集应用：判圈

并查集应用：判圈

Description

第一行输入正整数n,m,q表示一个有n个点m条边的无向图。q表示有q次询问。

接下来m行有m条边。每行两个u，v属于[1,n]范围的正整数，表示u,v之间有边。

接下来q行，每行两个点u,v,属于[1,n]。

如果（u，v）这条边已经存在或者如果加入这条边后会产生新的环，则输出一行YES,否则输出NO

Sample Input 1 

5 3 3
1 2
2 3
3 1
1 2
3 4
4 5

Sample Output 1

YES
NO
NO

来源：oj作业三

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        
        UnionFind unionfind= new UnionFind(n);
        Set<String> edge= new HashSet<>();//hashSet存放边集
        
        for(int i=1;i<=m;i++) {
        	int u=sc.nextInt();
        	int v=sc.nextInt();
        	edge.add(u+","+v);
        	edge.add(v+","+u);//无向图记得反向
        	unionfind.union(u, v);//加入并查集
        }
        
        for(int i=1;i<=q;i++) {
        	int u=sc.nextInt();
        	int v=sc.nextInt();
        	if(edge.contains(u+","+v)) {
        		System.out.println("YES");
        	}
        	else if(unionfind.find(u)==unionfind.find(v)) {
        		System.out.println("YES");
        	}
        	else {
        		System.out.println("NO");
        	}
        }
       
    }
}

//并查集
class UnionFind{
	private int[] parent;
	private int[] rank;//树高，用于减少递归次数
	
	public UnionFind(int n) {
		parent = new int[n+1];
		rank = new int[n+1];
		for(int i=1;i<=n;i++) {
			parent[i]=i;//初始每个节点的祖先节点都是自己
			rank[i]=1;//初始树高为1
		}
	}
	
	//查通过递归父节点，找到祖先节点，如果祖先节点是自己，说明是环
	public int find(int u) {
		if(parent[u]!=u) {
			parent[u]=find(parent[u]);
		}
		return parent[u];
		}

	public void union(int u,int v) {
		int rootU=find(u);
		int rootV=find(v);
		//为了维持树高，哪里的树更矮，就作为父节点
		if(rootU!=rootV) {
			if(rank[rootU]>rank[rootV]) {
				parent[rootV]=rootU;
			}else if(rank[rootU]<rank[rootV]) {
				parent[rootU]=rootV;
			}else {
				parent[rootV]=rootU;
				rank[rootU]++;
			}
		}
	}
	
}