如何理解POJ 1986 java代碼實現

今天就跟大家聊聊有關如何理解POJ 1986 java代碼實現，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

package pro.yao10_16LCA;

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

/**
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6

 * @author XASW
 *
 */
public class Main {
	
	
	static int T,N,Q,S,E,W,set[],vis[],D[],first[];
	static Node[] nodes;
	static List<Integer[]> arrayV[];
	
	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.valueOf(st.nextToken());
		Q = Integer.valueOf(st.nextToken());
		
		arrayV = new ArrayList[N+1];
		nodes = new Node[Q*2 +2];
		set = new int[N+1];
		vis = new int[N+1];
		D = new int[N+1];
		first = new int[N+1];
		
		for (int i = 0; i < N+1; i++) {
			arrayV[i] = new ArrayList<Integer[]>();
			set[i] = i;
			first[i] = -1;
		}
		for (int i = 0; i < Q *2 +2; i++) {
			nodes[i] = new Node();
		}
		
		for (int i = 1; i <= Q; i++) {
			st = new StringTokenizer(bf.readLine());
			S = Integer.valueOf(st.nextToken());
			E = Integer.valueOf(st.nextToken());
			W = Integer.valueOf(st.nextToken());

			arrayV[S].add(new Integer[] {E,W});
			arrayV[E].add(new Integer[] {S,W});
		}
		
		st = new StringTokenizer(bf.readLine());
		Q = Integer.valueOf(st.nextToken());
		
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(bf.readLine());
			S = Integer.valueOf(st.nextToken());
			E = Integer.valueOf(st.nextToken());

			add(S,E,i*2);
			add(E,S,i*2+1);
		}
		
		D[1] = 0;
		tarjan(1);
		
		for (int i = 0; i < Q; i++) {
			int id = i*2;
			int u = nodes[id].from;
			int v = nodes[id].to;
			int lca = nodes[id].lca;
			
			System.out.println(D[u] + D[v]-2*D[lca]);
		}
		
	}
	
	static void tarjan(int u) {
		vis[u] = 1;
		for (int i = 0; i < arrayV[u].size(); i++) {
			Integer[] s = arrayV[u].get(i);
			if(vis[s[0]]==1) continue;
			D[s[0]] = D[u]+s[1];
			tarjan(s[0]);
			join(s[0],u);
		}
		
		for (int i = first[u]; i != -1; i=nodes[i].next) {
			int v = nodes[i].to;
			if(vis[v]==0)continue;
			nodes[i].lca = nodes[i^1].lca = find(v);
		}
	}
	
	static void add(int u,int v,int cnt) {
		nodes[cnt].to = v;
		nodes[cnt].from = u;
		nodes[cnt].next = first[u];
		first[u] = cnt;
	}
	
	static int find(int a) {
		if(set[a] == a) {
			return set[a];
		}
		return set[a] = find(set[a]);
	}
	static void join(int a,int b) {
		int A = find(a);
		int B = find(b);
		if(A!=B) {
			set[A] = B;
		}
		
	}
	static class Node{
		int from;
		int to;
		int next;
		int lca;
	}
	
}

看完上述內容，你們對如何理解POJ 1986 java代碼實現有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。