제목 20: 인색 한 나라
2383 단어 알고리즘재시험 하여 비행기 에 오르다.
시간 제한:
1000 ms | 메모리 제한:
65535 KB
난이도:
3
묘사 하 다.
인색 한 나라 에는 N 개 도시 가 있 는데, 이 N 개 도시 사이 에는 N - 1 개의 길 만 이 N 개 도 시 를 연결한다.현재 Tom 은 S 번 도시 에 있 습 니 다. 그 는 이 나라 의 지 도 를 가지 고 있 습 니 다. 만약 에 자신 이 T 번 도 시 를 참관 하려 면 반드시 거 쳐 야 하 는 앞의 도시 가 몇 번 도시 인지 알 고 싶 습 니 다.
입력
첫 번 째 줄 에 정수 M 을 입력 하면 테스트 데이터 가 모두 M (1 < = M < = 5) 그룹 임 을 나타 낸다.
각 조 의 테스트 데이터 의 첫 줄 에 하나의 정수 N (1 < = N < = 100000) 과 하나의 정수 S (1 < = S < = 100000) 를 입력 하고 N 은 도시 의 총 개 수 를 나타 내 며 S 는 참관 자가 있 는 도시 의 번 호 를 나타 낸다.
다음 N - 1 줄 은 줄 마다 두 개의 정수 a, b (1 < = a, b < = N) 가 있 는데 이것 은 a 번 도시 와 b 번 도시 사이 에 하나의 길이 연결 되 어 있다 는 것 을 나타 낸다.
출력
각 조 의 테스트 데 이 터 는 N 개의 정수 에 지 는데 그 중에서 i 번 수 는 S 에서 i 번 도시 로 가 려 면 반드시 거 쳐 야 하 는 이전 도시 의 번 호 를 나타 낸다.(그 중 i = S 시 출력 - 1)
샘플 입력
1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7
샘플 출력
-1 1 10 10 9 8 3 1 1 8
근원
고전 제목
/*********************************
* :2013-3-26
* :SJF0115
* : 20:
* :http://acm.nyist.net/JudgeOnline/problem.php?pid=20
* :AC
* : OJ
* :
**********************************/
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
vector<int> G[100001];
int preCity[100001];
int vis[100001];
//
void DFS(int location){
vis[location] = 1;
// location
for(int i = 0;i < G[location].size();i++){
int v = G[location][i];
if(!vis[v]){
//
preCity[v] = location;
//printf("%d %d
",location,v);
DFS(v);
}
}
}
int main ()
{
int N,M,City,Location,a,b,i,first;
//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);
scanf("%d",&N);
while (N--){
scanf("%d %d",&City,&Location);
//
for(i = 1;i <= City;i++){
G[i].clear();
}
//
for(i = 1;i < City;i++){
scanf("%d %d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
//
memset(vis,0,sizeof(vis));
vis[Location] = 1;
preCity[Location] = -1;
DFS(Location);
//
first = 1;
for(i = 1;i <= City;i++){
if(first){
first = 0;
}
else{
printf(" ");
}
printf("%d",preCity[i]);
}
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.