結果

問題 No.416 旅行会社
ユーザー ei1333333
提出日時 2016-08-23 00:48:36
言語 Java
(openjdk 23)
結果
AC  
実行時間 2,639 ms / 4,000 ms
コード長 2,480 bytes
コンパイル時間 2,408 ms
コンパイル使用メモリ 79,992 KB
実行使用メモリ 124,832 KB
最終ジャッジ日時 2024-12-14 19:44:11
合計ジャッジ時間 33,838 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main
{
		Scanner cin;
		int N, M, Q;
		int[] A, B, C, D, ret;
		boolean[] V;
		List< HashMap< Integer, Integer > > edgeIdx;
		UnionFind tree;
		List< Queue < Integer > > que;
		
		public static void main(String[] arg)
		{
				new Main().Solve();
		}

		public void Solve()
		{
				cin = new Scanner(System.in);
				
				N = cin.nextInt();
			   M = cin.nextInt();
			   Q = cin.nextInt();
				
				A = new int[M];
				B = new int[M];
			   C = new int[Q];
			   D = new int[Q];

				ret = new int[N];
				 
				V = new boolean[M];
				
			   edgeIdx = new ArrayList<>();
				for(int i = 0; i < N; i++) {
						edgeIdx.add(new HashMap<>());
				}
				
			   tree = new UnionFind(N);

			   que = new ArrayList<>();
				for(int i = 0; i < N; i++) {
						que.add(new ArrayDeque< Integer >());
						que.get(i).add(i);
				}
				
				for(int i = 0; i < M;i++) {
						A[i] = cin.nextInt() - 1;
						B[i] = cin.nextInt() - 1;
						edgeIdx.get(A[i]).put(B[i], i);
				}
				
				for(int i = 0; i < Q; i++) {
						C[i] = cin.nextInt() - 1;
						D[i] = cin.nextInt() - 1;
						V[edgeIdx.get(C[i]).get(D[i])] = true;
				}

				for(int i = 0; i < M; i++) {
						if(!V[i]) Merge(A[i], B[i]);
				}

				
				int root = tree.find(0);
				while(!que.get(root).isEmpty()) {
						ret[que.get(root).poll()] = -1;
				}
				
				for(int i = Q - 1; i >= 0; i--) {
						Merge(C[i], D[i]);
						root = tree.find(0);
						while(!que.get(root).isEmpty()) {
								ret[que.get(root).poll()] = i + 1;
						}
				}

				for(int i = 1; i < N; i++) {
						System.out.println(ret[i]);
				}
		}

		public void Merge(int p, int q)
		{
			   p = tree.find(p);
				q = tree.find(q);
				if(p != q) {
						if(que.get(p).size() < que.get(q).size()) {
								while(!que.get(p).isEmpty()) {
										que.get(q).add(que.get(p).poll());
								}
								tree.unite(q, p);
						} else {
								while(!que.get(q).isEmpty()) {
										que.get(p).add(que.get(q).poll());
								}
								tree.unite(p, q);
						}
				}
				return;
		}
		

		public class UnionFind
		{
				int[] data;

				UnionFind(int sz)
				{
						data = new int[sz];
						Arrays.fill(data, -1);
				}
				int find(int y)
				{
						if(data[y] < 0) return(y);
						return(data[y] = find(data[y]));
				}
				int unite(int x, int y)
				{
						x = find(x);
						y = find(y);
						if(x != y) {
								data[x] += data[y];
								data[y] = x;
						}
						return(find(x));
				}

		}
}
0