POJ1988带权并查集

本文主要是介绍POJ1988带权并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

M u v 将u所在的堆移动到v所在的堆的上面

C u 求u的下面有多少块

带权并查集

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;public class Main {public static void main(String[] args){new Task().solve() ;		}
}class Task{final int N = 30000 ;int[] size = new int[N+8] ;int[] high = new int[N+8] ;int[] father = new int[N+8] ;void init(){for(int i = 1 ; i <= N ; i++){father[i] = i ;size[i] = 1 ;high[i] = 0 ;}}int getFather(int u){if(father[u] == u) return u ;int fu = father[u] ;int root = getFather(fu) ;high[u] += high[fu] ;return father[u] = root ;}void merge(int from , int to){int rootFrom = getFather(from) ;int rootTo = getFather(to) ;high[rootTo] = size[rootFrom] ;size[rootFrom] += size[rootTo] ;father[rootTo] = father[rootFrom] ;}   void solve(){init() ;int p = in.nextInt() ;while(p-- > 0){if("M".equals(in.next())){int from = in.nextInt() ;int to = in.nextInt() ; merge(from, to) ;}else{int u = in.nextInt() ;int root = getFather(u) ;out.println(size[root] - high[u] - 1) ;} }out.flush() ;}InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;
}class InputReader {  public BufferedReader reader;  public StringTokenizer tokenizer;  public InputReader(InputStream stream) {  reader = new BufferedReader(new InputStreamReader(stream), 32768);  tokenizer = new StringTokenizer("");  }  private void eat(String s) {  tokenizer = new StringTokenizer(s);  }  public String nextLine() {  try {  return reader.readLine();  } catch (Exception e) {  return null;  }  }  public boolean hasNext() {  while (!tokenizer.hasMoreTokens()) {  String s = nextLine();  if (s == null)  return false;  eat(s);  }  return true;  }  public String next() {  hasNext();  return tokenizer.nextToken();  }  public int nextInt() {  return Integer.parseInt(next());  }  public long nextLong() {  return Long.parseLong(next());  }  public double nextDouble() {  return Double.parseDouble(next());  }  public BigInteger nextBigInteger() {  return new BigInteger(next());  }  }  

这篇关于POJ1988带权并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---