친구 권 (집합)
1631 단어 병 찰 집
입력 형식:
입력 한 첫 줄 은 두 개의 정수 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);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
항 저 우 전기 1878 오 라 회 로 (오 라 회 로 의 판단)오 라 회 로 는 펜 이 지면 을 떠 나 지 못 하 게 그림 의 각 변 을 한 번 만 그 릴 수 있 고 출발점 으로 돌아 갈 수 있 는 회 로 를 말한다.이제 오 라 회 로 가 있 는 지 그림 을 정 해 주 시 겠 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.