pta 문제 집 5 - 16 친구 권

1764 단어 pat병 찰 집
한 학교 에는 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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
int n,m;
int father[30005];
int find(int x)
{
	if(father[x]!=x)
		father[x]=find(father[x]);
	else
		return father[x];
}
int ans[30005];
int main()
{
	scanf("%d%d",&n,&m);
	int x;
	int y;
	for(int i=1;i<=n;i++)
		father[i]=i;

	for(int i=1;i<=m;i++)
	{
		scanf("%d",&x);
		int yy=0;
		for(int j=1;j<=x;j++)
		{
			scanf("%d",&y);
			if(yy!=0)
			{
				int fx=find(yy);
				int fy=find(y);
				father[fx]=fy;
			}
			else
				yy=y;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int fa=find(i);
		ans[fa]++;
	}
	sort(ans+1,ans+n+1);
	printf("%d
",ans[n]);
	return 0;
}
선분 수 입문 [단점 갱신] 적병 포진 HDU 1166
경사 율 0 이하 의 연결선 수량 - 병합 정렬

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage