친구 권 (집합)

1631 단어 병 찰 집
한 학교 에는 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

이 문 제 는 집 을 이용 하여 조사 할 수 있다. 친구 들 끼 리 연결 해서 나무 만 들 기.  그리고 각 번호 가 있 는 나무의 뿌리 를 찾 으 면 됩 니 다.
어느 나무 가 가장 많이 점 을 찍 는 지 보면 된다.
 AC 코드:
#include
#include
using namespace std;
int pre[30005];
int sum[30005];
int find(int x){
	if(x==pre[x])
	return x;
	else return pre[x]=find(pre[x]);
}
void merge(int x,int y){
int a=find(x);
int b=find(y);
if(a!=b) pre[b]=a;
}
int main(){
	int n,m,p,x,y;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) pre[i]=i;
	while(m--){
		scanf("%d",&p);
		for(int i=1;i<=p;i++){
			if(i==1)
			scanf("%d",&x);
			else{
				scanf("%d",&y);
				merge(x,y);
			}
		}
	}
    for(int i=1;i<=n;i++) find(i);//       ,         ,               
    /*
    7 2
    3 1 2 3
    2 4 2*/
	for(int i=1;i<=n;i++)
	sum[pre[i]]++;
	int ans=0;
	for(int i=1;i<=n;++i)
	ans=max(ans,sum[i]);
	printf("%d
",ans); }

좋은 웹페이지 즐겨찾기