POJ1703带权并查集

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

D： u v  u与v在不同的集合

A： u v  查询u与v的关系

1)压缩路径过程
       fu->root   0  1 
u-fu


0                 0  1  
1                 1  0


2)合并过程 fu->fv


     u->fu   0 1  
v->fv
0            1 0
1            0 1

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 {InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);int[] father ;int[] high ;int getFather(int u){if(u == father[u]) return u ;int fu = father[u] ;int root = getFather(fu) ;high[u] = (high[u] + high[fu]) % 2 ;return father[u] = root ;}void solve() {int t = in.nextInt();while (t-- > 0) {int n = in.nextInt();int m = in.nextInt();father = new int[n + 1];high = new int[n + 1];for(int i = 1 ; i <= n ; i++){father[i] = i ;high[i] = 0 ;}while (m-- > 0) {String type = in.next() ;int u = in.nextInt() ;int v = in.nextInt() ;if ("A".equals(type)) {int fu = getFather(u) ;int fv = getFather(v) ;if(n == 2){out.println("In different gangs.") ;continue ;}if(fu != fv) out.println("Not sure yet.") ;else out.println((high[u]%2 == high[v]%2) ? "In the same gang." : "In different gangs.") ;}else{int fu = getFather(u) ;int fv = getFather(v) ;father[fu] = fv ;high[fu] = 1 - (high[u] ^ high[v]) ;}}out.flush() ;}}}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());}}

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

---