9 도 OJ: 제목 1012 원활 한 공사
모 성 은 도시 의 교통 상황 을 조사 하여 기 존의 도시 도로 통계 표를 얻 었 고 표 에는 모든 도로 가 직접 연 결 된 도시 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 도시 간 에 도 교통 을 실현 할 수 있 도록 하 는 것 이다.-- 최소한 몇 개의 도 로 를 더 건설 해 야 하나.
입력:
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 사례 의 첫 번 째 줄 은 두 개의 정 수 를 제시 하 는데 그것 이 바로 도시 수량 N (< 1000) 과 도로 수량 M 이다.그 다음 에 M 줄 은 M 개의 도로 에 대응 하고 각 줄 은 한 쌍 의 정 수 를 제시 하 는데 각각 이 도로 가 직접 연 결 된 두 도시 의 번호 이다.간단하게 말하자면, 도 시 는 1 부터 N 까지 번호 가 있다. 주의: 두 도시 사이 에 여러 개의 길이 통 할 수 있 습 니 다. 즉, 3 3 1 2 1 2 2 1 이런 입력 도 합법적이다 N 이 0 일 때 입력 이 끝나 면 이 용례 는 처리 되 지 않 습 니 다.
출력:
각 테스트 사례 에 대해 서 는 1 줄 에서 최소 건설 해 야 할 도로 수 를 출력 한다.
샘플 입력:
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0샘플 출력:
1
0
2
998[문제 풀이 아이디어!]
1. 이 문 제 는 전형 적 인 문 제 를 수집 하 는 것 이다.
2. 그림 (그림 을 만 들 필요 가 없 음) 의 연결 지점 수 를 구하 면 건설 해 야 하 는 다리 의 수 는 연결 지점 수 에서 1 을 빼 면 된다.
3. 연 결 된 코드 는
/*
* x, a[x]=x
* a[x]=x
* x1 x2 ,x2 x3 , a[x1],a[2],a[3]
* while()
*/
int find(int x)
{
while(a[x]!=x)
x=a[x];
return x;
}[제목 의 AC 코드]
<span style="font-size:18px;">#include<stdio.h>
int a[1024]={0};
/*
* x, a[x]=x
* a[x]=x
* x1 x2 ,x2 x3 , a[x1],a[2],a[3]
* while()
*/
int find(int x)
{
while(a[x]!=x)
x=a[x];
return x;
}
int main(){
int m,n;
while(scanf("%d",&n)==1&&n){
scanf("%d",&m);
bool sign[1024]={0};
int i,j;
for(i=1;i<=n;i++) a[i]=i;
for(i=0;i<m;i++){
int s,e;
scanf("%d %d",&s,&e);
int fx=find(s);
int fy=find(e);
if(fx!=fy) a[fx]=fy;
}
int count=0;
for(i=1;i<=n;i++){
if(a[i]==i) count++;
}
printf("%d
",count-1);
}
}</span>[제목 사이트]
http://ac.jobdu.com/problem.php?pid=1012
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
