L2-4 tribe (25 points)

In a community, everyone has their own small circle, and may belong to many different circles of friends at the same time. We think that friends of friends are all included in a tribe, so we need to ask you to count, in a given community, how many tribes do not intersect each other? And check whether any two people belong to the same tribe.

Input format:

Enter a positive integer NNN (≤ 104\le 10^4 ≤ 10 4) in the first line, which is the number of known small circles. Then NNN lines, each line giving a small circle of people in the following format:

KKK P[1]P[1]P[1] P[2]P[2]P[2] ⋯\cdots⋯ P[K]P[K]P[K]

Where KKK is the number of people in the small circle, P[i]P[i]P[i] (i=1,..., Ki = 1, cdots, Ki = 1,..., K) is the number of everyone in the small circle. Here, the number of all people starts from 1, and the maximum number will not exceed 10410 ^ 410 4.

The next line gives a non negative integer QQQ (≤ 104\le 10^4 ≤ 10 4), which is the number of queries. Then QQQ lines, each line gives a pair of people's number to be queried.

Output format:

First, output the total number of people in this community and the number of tribes that do not intersect each other in one line. Then for each query, if they belong to the same tribe, output Y in one line, otherwise output N.

Input example:

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

Output example:

10 2
Y
N

Two test points timeout

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

//** Class for buffered reading int and double values *//*
class Reader {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	// ** call this method to initialize reader for InputStream *//*
	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	// ** get next word *//*
	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens()) {
			// TODO add check for eof if necessary
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
	static boolean hasNext()throws IOException {
		return tokenizer.hasMoreTokens();
	}
	static String nextLine() throws IOException{
		return reader.readLine();
	}
	static char nextChar() throws IOException{
		return next().charAt(0);
	}
	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static float nextFloat() throws IOException {
		return Float.parseFloat(next());
	}
}
public class Main {
	private static int[]a;
	public static void main(String[] args) throws IOException {
		Reader.init(System.in);
		int n = Reader.nextInt();
		Set<Integer>set = new HashSet<Integer>();
		a = new int[10001];
		for (int i = 1; i < a.length; i++) {
			a[i] = i;
		}
		input(n,set);
		int q = Reader.nextInt();
		int cnt = 0;
		for (int i = 1; i <= set.size(); i++) {
			if(a[i]==i)cnt++;
		}
		System.out.println(set.size()+" "+cnt);
		for (int i = 0; i < q; i++) {
			int node1 = Reader.nextInt();
			int node2= Reader.nextInt();
			if (find(node1)==find(node2)) {
				System.out.println("Y");
			}else {
				System.out.println("N");
			}
		}
	}
	static void input(int n, Set<Integer> set) throws IOException {
		for (int i = 0; i < n; i++) {
			int k = Reader.nextInt();
			int a = Reader.nextInt();
			set.add(a);
			for (int j = 1; j < k; j++) {
				int b = Reader.nextInt();
				set.add(b);
				join(a,b);
			}
		}
	}
	static int find(int x) // Find root node
	{
		int r = x;
		while (a[r] != r) // Return to root node r
			r = a[r];
		int i = x, j;
		while (i != r) // Path compression
		{
			j = a[i]; // Record his value with the temporary variable j before changing his superior
			a[i] = r; // Change superior to root
			i = j;
		}
		return r;
	}

	static void join(int x, int y) // Determine whether x y is connected,
	// If it's connected, it doesn't matter. If it's not connected, merge the connected branches,
	{
		int fx = find(x), fy = find(y);
		if (fx != fy)
			a[fx] = fy;
	}
}



Published 45 original articles, won praise 8, visited 1757

Tags: Java

Posted on Thu, 30 Jan 2020 00:28:11 -0800 by s2r