Nyoj - 20 인색 한 나라
2708 단어 데이터 구조
시간 제한:
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
주로 dfs 검색 을 사용 합 니 다. 그림 의 구축 은 인접 표 로 해 야 합 니 다. 행렬 은 그렇게 큰 것 을 만 들 수 없 을 것 같 습 니 다.
그림 이 만들어 진 후에 입력 의 시작 점 을 뿌리 노드 로 하면 생 성 트 리 를 얻 을 수 있 고 뿌리 노드 부터 검색 할 수 있 습 니 다.
답 을 저장 하기 위해 int ans [100005] 배열 을 만 듭 니 다.
예 를 들 어 현재 노드 3, 3 의 아래 에 세 글자 노드 6, 8, 9 가 있 으 면 ans [6] = ans [8] = ans [9] = 3 을
이렇게 옮 겨 다 니 면 현재 노드 에 부분 이 없 으 면 되 돌아 가 고 마지막 순환 이 끝나 면 답 도 나온다.
주의해 야 할 것 은 방문 한 노드 를 표시 하 는 것 을 잊 지 마 세 요. 방향 이 없 는 그림 이기 때문에 표시 하지 않 으 면 순환 합 니 다.
또 하 나 는 vector 로 그림 을 만 들 면 구축, 방문, 조작 이 든 프로그램의 선명 도가 크게 개선 된다.
그리고 실수 할 가능성 을 크게 낮 출 수 있 습 니 다.
나중에 시간 이 있 으 면 stl 의 사용 기 교 를 정리 하려 고 합 니 다.
마지막 으로 본 문제 의 코드 입 니 다.
#include
#include
#include
#include
#include
#include
using namespace std;
vector map[100005]; // 100005
int ans[100005];
bool vis[100005];
int n;
int f(int beg)
{
if(map[beg].size()==0) return 0; //
vis[beg]=true;
for(int i=0;i!=map[beg].size();++i)//
{
if(vis[map[beg][i]]) continue;// ( !
ans[map[beg][i]]=beg;
f(map[beg][i]);
}
return 0;
}
int main()
{
int num,root;
scanf("%d",&num);
while(num--!=0)
{
scanf("%d%d",&n,&root);
for(int i=1;i<=n;++i)//
{
map[i].clear();
}
for(int i=1;i!=n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
map[a].push_back(b);//
map[b].push_back(a);
}
memset(ans,0,sizeof(ans));//
memset(vis,0,sizeof(vis));
ans[root]=-1;
f(root);
printf("%d",ans[1]);//
for(int i=2;i<=n;++i)
{
printf(" %d",ans[i]);
}
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.