PTA 7 - 2 모멘트 (25 점)

한 학교 에는 N 명의 학생 이 있어 M 개의 클럽 을 만 들 었 다.각 클럽 의 학생 들 은 어느 정도 비슷 한 취 미 를 가지 고 친구 권 을 형성한다.한 학생 은 여러 개의 다른 클럽 에 동시에 속 할 수 있다.'내 친구 의 친구 도 내 친구' 라 는 추론 에 따 르 면 A 와 B 가 친구 이 고 B 와 C 가 친구 라면 A 와 C 도 친구 라 는 것 을 알 수 있다.최대 친구 권 에 몇 명 이 있 는 지 계산 하 는 프로그램 을 만들어 보 세 요.
입력 형식:
입력 한 첫 줄 은 두 개의 정수 N (≤ 30000) 과 M (≤ 1000) 을 포함 하고 각각 학교의 학생 총수 와 클럽 의 개 수 를 대표 한다.뒤의 M 줄 은 각 줄 마다 다음 과 같은 형식 으로 1 개의 클럽 의 정 보 를 제공 하 는데 그 중에서 학생 들 은 1 ~ N 번호 에서 i Mi（ ） 1（ ） 2 … Mi
출력 형식:
출력 은 최대 친구 권 에 몇 명 이 있 는 지 를 나타 내 는 정 수 를 보 여 줍 니 다.
입력 예시:

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

출력 예시:

4

가장 일반적인 것 을 수집 하여 문 제 를 풀다.
코드 는 다음 과 같 습 니 다:

#include 
using namespace std;
typedef struct node
{
	int data;
	int rank;
	int parent;
}UFSTree;

void MAKE_SET(UFSTree t[], int n)
{
	int i;
	for (i = 0; i <= n; i++)
	{
		t[i].data = i;
		t[i].rank = 0;
		t[i].parent = i;
	}
}

int FIND_SET(UFSTree t[], int x)
{
	if (x != t[x].parent)
		return(FIND_SET(t, t[x].parent));
	else
		return x;
}

void UNION(UFSTree t[], int x, int y)
{
	x = FIND_SET(t, x);
	y = FIND_SET(t, y);
	if (t[x].rank > t[y].rank)
		t[y].parent = x;
	else
	{
		t[x].parent = y;
		if (t[x].rank == t[y].rank)
			t[y].rank++;
	}
}

int main() 
{
	int N, M;
	cin >> N >> M;
	UFSTree P[30001];
	MAKE_SET(P, N);
	for (int i = 0; i < M; i++)
	{
		int n,M[30001];
		cin >> n >> M[0];
		for (int j = 1; j < n; j++)
		{
			cin >> M[j];
			UNION(P, M[j - 1], M[j]);
		}
	}

	int Max[30001] = { 0 };
	for (int k = 1; k <= N; k++)
		Max[FIND_SET(P, k)]++;

	int MA = 0;
	for (int p = 1; p <= N; p++)
		MA = MA > Max[p] ? MA : Max[p];

	cout << MA;
	return 0;
}