7 - 5 모멘트 (25 점)

11140 단어 #데이터 구조병 찰 집
한 학교 에는 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
1
2
3
4
5

출력 예시:
4

#include
using namespace std;
const int maxn = 1e5+10;
int pre[maxn];
int find(int x){
     
	return x==pre[x]?x:pre[x]=find(pre[x]);
}
void unio(int x,int y){
     
	x=find(x);
	y=find(y);
	if(x==y) return;
	pre[x]=y;
}
int main(){
     
	int n,m,maxNum=0;
	scanf("%d %d",&n,&m);
	for( int i=0; i<=n; i++ ) pre[i]=i;
	for( int i=0; i<m; i++ ){
     
		vector<int>v;
		int num,x;
		scanf("%d",&num);
		for( int j=0; j<num; j++ ){
     
			scanf("%d",&x);v.push_back(x);
		}
		if(num>=2){
     
			for( int j=0; j<num; j++ ){
     
				for( int k=j+1; k<num; k++ ){
     
					unio(v[j],v[k]);
				}
			}
		}
	}
	map<int,int>mpp;
	for( int i=1; i<=n; i++ ) mpp[find(i)] +=1;
	for( map<int,int>::iterator it = mpp.begin(); it !=mpp.end(); it++ ) maxNum = max(maxNum,it->second);
	printf("%d",maxNum);
}
hrbeu 1318 X ^ a mod b = c 2 차 남 음
mysql 변수 소개

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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