Submission #3728780

---

Source Code Expand

import java.util.Scanner;

class Main{
	static boolean[] kankei;
	static int N;
	static boolean[][] rinsetu;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		int M=sc.nextInt();
		rinsetu=new boolean[N+1][N+1];
		for(int i=0;i <=N; i++) {
			for(int j=0; j<=N; j++) {
				rinsetu[i][j]=false;
			}
		}

		for(int i=0; i<M; i++) {
			int from=sc.nextInt();
			int to=sc.nextInt();
			rinsetu[from][to]=true;	//有向グラフ
		}
		UnionFind.init(13);

		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(i!=j) {
					if(rinsetu[i][j] || rinsetu[j][i]) {
						UnionFind.unite(i, j);
					}
				}
			}
		}
		int max=1;
		int tmp=1;
		for(int i=1; i<=12; i++) {
			tmp=1;
			for(int j=1; j<=12; j++) {
				if(i!=j) {
					if(UnionFind.same(i,j)) {
						tmp++;
					}
				}
			}
			max=Math.max(max, tmp);
		}
		System.out.println(max);
		sc.close();
	}
	static class UnionFind {
		static int N;			//頂点数
		static int par[];		//親ノード
		static int rank[];		//ランク　UnionFind木の高さがrankみたい
		public static void init(int n) {		//初期化
			N = n;
			par = new int[N];
			rank = new int[N];
			for(int i = 0; i < N; i++) {		//0処理
				par[i] = i;
				rank[i] = 0;
			}
		}

		public static int find(int x) {		//木の根を求める
			if(par[x] == x) {
				return x;
			} else {
				return par[x] = find(par[x]);
			}
		}

		public static void unite(int x, int y) {		//xとyの属する集合を併合	xにyをという意味合いが強そう		集合に含めるときに unite(114,514);のようにするみたい
			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]++;
			}
		}

		public static boolean same(int x, int y) {		//x,yが同じ集合に属するか否か
			return find(x) == find(y);
		}
	}
}

Submission Info

Judge Result