初识CSS
吝啬的国度
- 描述
- 在一个吝啬的国度里有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
-
该题就是将图用邻接表建立起来后,直接进行深搜一遍就完事!
- 比较简单, 直接附代码:
-
-
- #include <stdio.h>
- #include <stdlib.h>
- #include <queue>
- #include <iostream>
- #define Max 100001
- using namespace std;
- typedef struct ele{
- int v;
- struct ele *next;
- }ele;
- int parent[Max];
- int N;
- typedef struct Graph {
- ele *vertex;
- }Graph;
- void bfs(int v, Graph *g);
- void insert_graph (Graph *g, int a, int b);
- void init_graph (Graph *g);
- int main (){
- Graph g[100001];
- int M, S;
- int a, b, i;
- scanf("%d", &M);
- while (M--){
- scanf("%d %d", &N, &S);
- init_graph(g);
- for(i = 0 ; i < N - 1; i++){
- scanf("%d %d", &a, &b);
- insert_graph (g, a, b);
- }
- bfs(S, g);
- parent[S] = -1;
- for(i = 1; i <= N; i++) {
- printf("%d ", parent[i]);
- }
- printf("\n");
- }
- }
- void bfs(int v, Graph *g){
- queue <int>q;
- int i, var;
- ele *e;
- int visited[Max] = {0};
- q.push(v);
- while(!q.empty()){
- var = q.front();
- q.pop();
- for(e = g[var].vertex; e != NULL; e = e -> next){
- if(!visited[e -> v]){
- visited[e -> v] = 1;
- parent[e ->v] = var;
- q.push(e -> v);
- }
- }
- }
- }
- void insert_graph(Graph *g, int a, int b){
- ele *temp = (ele *) malloc (sizeof(ele));
- ele *temp1 = (ele *) malloc (sizeof(ele));
- temp -> v = b;
- temp1 ->v = a;
- if(g[a].vertex == NULL){
- g[a]. vertex = temp;
- temp -> next = NULL;
- }
- else{
- temp -> next = g[a].vertex;
- g[a].vertex = temp;
- }
- if(g[b].vertex == NULL) {
- g[b].vertex = temp1;
- temp1 -> next = NULL;
- }
- else{
- temp1 ->next = g[b].vertex;
- g[b].vertex = temp1;
- }
- }
- void init_graph(Graph *g){
- int i;
- for(i = 0; i <= N; i++){
- g[i].vertex = NULL;
- }
- }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。