sdutacm - 여러분, 빨리 와 주세요. A 문제.
1723 단어 ACM 데이터 구조 트 리-최소 생 성 트 리병 찰 집
Time Limit: 1000MS MemoryLimit: 65536KB
SubmitStatistic
ProblemDescription
해상 에는 N (1 & lt; = N & gt; = 2000) 개의 섬 이 있 고, 번 호 는 1 부터 N 까지 이 며, 같은 부락의 섬 들 사이 에는 직간 접적 인 길이 연결 되 어 있어 서로 다른 부락 간 에는 길이 없다.이제 M (1 < = M < = N * (N - 1) / 2) 길 을 드 립 니 다.이 해역 에 모두 몇 개의 부족 이 있 는 지 물 었 다.
Input
다 중 입력.각 조 의 첫 줄 에 N, M 을 입력 하 십시오.그 다음 에 M 줄 은 줄 마다 두 개의 정수 u, v 는 섬 u 와 v 사 이 를 대표 하 는 길이 있다.
Output
각 조 의 데 이 터 는 하나의 정 수 를 출력 하여 부족 수 를 대표 한다.
ExampleInput
3 1
1 2
3 2
1 2
1 3
ExampleOutput
2
1
Hint
Author
#include
#include
using namespace std;
int f[3000]={0},n,m,k,sum;
int getf(int v)
{
if(f[v]==v)
{
return v;
}
else
{
f[v] = getf(f[v]);
return f[v];
}
}
void amerge(int l,int r)
{
int t1,t2;
t1 = getf(l);
t2 = getf(r);
if(t1!=t2)
{
f[t2] = t1;
}
return ;
}
int main()
{
int x,y,i;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
{
f[i] = i;
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
amerge(x,y);
}
sum = 0;
for(i = 1;i<=n;i++)
{
if(f[i]==i)
{
sum++;
}
}
printf("%d
",sum);
}
return 0;
}
/***************************************************
User name: jk160505
Result: Accepted
Take time: 12ms
Take Memory: 168KB
Submit time: 2017-02-17 10:23:54
****************************************************/ 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
작은 흠 의 성옛날 에 한 국왕 이 있 었 는데 그 는 작은 흠 이 라 고 불 렀 다.어느 날, 그 는 성 을 지 으 려 고 했 습 니 다. 주로 방 의 연 결 된 도면 입 니 다.작은 흠 은 임의의 두 방 이 있 고 하나의 경로...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
