7 - 4 모멘트 (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
출력 예시:
#include
int pre[30001];
int sum[30001];
int ans=0;
void init(int n)
{
for(int i=1;i<=n;i++)
{
pre[i]=i;
sum[i]=1;
}
}
int find(int x)
{
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);//
}
void join(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
pre[fx]=fy;
sum[fy]+=sum[fx];
}
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
init(n);
int s;
while(m--)
{
scanf("%d",&s);
int stus[s+1];
for(int i=1;i<=s;i++)
{
scanf("%d",&stus[i]);
}
for(int x=1;x<=s;x++)
{
for(int z=x+1;z<=s;z++)
{
join(stus[x],stus[z]);
}
}
}
int max=0;
for(int i=1;i<=n;i++)
{
if(sum[i]>max)max=sum[i];
}
printf("%d",max);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
