Submission #101844

---

Source Code Expand

import static java.lang.System.in;
import static java.lang.System.out;

import java.io.*;
import java.util.*;

public class Main {
	static final double EPS = 1e-10;
	static final double INF = 1 << 31;
	static final double PI = Math.PI;

	public static Scanner sc = new Scanner(in);
	StringBuilder sb = new StringBuilder();
	BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));

	static final String br = System.getProperty("line.separator");
	
	public static class UnionFind{
		public int[] par,rank;
		public int size;
		public UnionFind(int n){
			par=new int[n];
			for(int i=0;i<n;i++)par[i]=i;
			rank=new int[n];
			size=n;
		}
		public int find(int x){
			if(par[x]==x)return x;
			return par[x]=find(par[x]);
		}
		public boolean same(int x,int y){
			return find(x)==find(y);
		}
		public void unite(int x,int y){
			x=find(x);y=find(y);
			if(x==y)return;

			if(rank[x]<rank[y])par[x]=y;
			else par[y]=x;
			if(rank[x]==rank[y]) rank[x]++;
			size--;
		}
	}
	
	class Edge{
		int f,t;
		Edge(int _f,int _t){
			f=_f;t=_t;
		}
	}
	
	class Task{
		int k;
		int e;
		int v;
		int w;
		Task(int _k,int _e){
			k=_k;e=_e;
		}
		Task(int _k,int _v,int _w){
			k=_k;v=_v;w=_w;
		}
		
	}
	
	
	public void run() throws IOException {
		int N=sc.nextInt(),M=sc.nextInt(),K=sc.nextInt();
	
		Edge[] es=new Edge[M];
		for(int i=0;i<M;i++){
			es[i]=new Edge(sc.nextInt()-1,sc.nextInt()-1);
		}
		Task[] tasks=new Task[K];
		
		for(int i=0;i<K;i++){
			int k=sc.nextInt();
			if(k==0){
				tasks[i]=new Task(k,sc.nextInt()-1);
			}else{
				tasks[i]=new Task(k,sc.nextInt()-1,sc.nextInt()-1);			
			}
		}

		boolean[] ex=new boolean[M];
		Arrays.fill(ex,true);
		for(int i=0;i<K;i++){
			if(tasks[i].k==0){
				ex[tasks[i].e]=false;
			}
		}
		
		UnionFind uf=new UnionFind(N);
		for(int i=0;i<M;i++){
			if(ex[i]){
				uf.unite(es[i].f,es[i].t);
			}
		}
		
		List<String> res=new ArrayList<String>();
		
		
		for(int i=K-1;i>=0;i--){
			if(tasks[i].k==0){
				int ei=tasks[i].e;
				uf.unite(es[ei].f,es[ei].t);
			}else{
				if(uf.same(tasks[i].v, tasks[i].w)){
					res.add("YES");
				}else{
					res.add("NO");					
				}
			}			
		}
		
		for(int i=res.size()-1;i>=0;i--){
			sb.append(res.get(i)+br);
		}
		pr(sb);
	}

	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	public static void pr(Object obj) {
		out.print(obj);
	}
	public static void ln(Object obj) {
		out.println(obj);
	}
}

Submission Info

Judge Result