初识CSS

吝啬的国度

时间限制: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

该题就是将图用邻接表建立起来后,直接进行深搜一遍就完事!

比较简单, 直接附代码:

  1.    
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. #include <queue>  
  5. #include <iostream>  
  6. #define Max 100001  
  7.   
  8. using namespace std;  
  9.   
  10. typedef struct ele{  
  11.     int v;  
  12.     struct ele *next;  
  13. }ele;  
  14.   
  15. int parent[Max];  
  16. int N;  
  17. typedef struct Graph {  
  18.     ele *vertex;  
  19. }Graph;  
  20.   
  21. void bfs(int v, Graph *g);  
  22. void insert_graph (Graph *g, int a, int b);  
  23. void init_graph (Graph *g);  
  24.   
  25. int main (){  
  26.       
  27.     Graph g[100001];  
  28.     int M, S;  
  29.     int a, b, i;  
  30.   
  31.     scanf("%d", &M);  
  32.     while (M--){  
  33.         scanf("%d %d", &N, &S);  
  34.         init_graph(g);  
  35.         for(i = 0 ; i < N - 1; i++){  
  36.             scanf("%d %d", &a, &b);  
  37.             insert_graph (g, a, b);  
  38.         }  
  39.         bfs(S, g);  
  40.         parent[S] = -1;  
  41.         for(i = 1; i <= N; i++) {  
  42.             printf("%d ", parent[i]);  
  43.         }  
  44.         printf("\n");  
  45.     }  
  46. }  
  47.   
  48. void bfs(int v, Graph *g){  
  49.       
  50.     queue <int>q;  
  51.     int i, var;  
  52.     ele *e;  
  53.     int visited[Max] = {0};  
  54.       
  55.     q.push(v);  
  56.           
  57.     while(!q.empty()){  
  58.         var = q.front();  
  59.         q.pop();  
  60.         for(e = g[var].vertex; e != NULL; e = e -> next){  
  61.             if(!visited[e -> v]){  
  62.                 visited[e -> v] = 1;  
  63.                 parent[e ->v] = var;  
  64.                 q.push(e -> v);  
  65.             }  
  66.         }  
  67.     }  
  68. }  
  69. void insert_graph(Graph *g, int a, int b){  
  70.       
  71.     ele *temp = (ele *) malloc (sizeof(ele));  
  72.     ele *temp1 = (ele *) malloc (sizeof(ele));  
  73.     temp -> v = b;  
  74.     temp1 ->v = a;  
  75.     if(g[a].vertex == NULL){  
  76.         g[a]. vertex = temp;  
  77.         temp -> next = NULL;  
  78.     }  
  79.     else{  
  80.         temp -> next = g[a].vertex;  
  81.         g[a].vertex = temp;  
  82.     }  
  83.       
  84.     if(g[b].vertex == NULL) {  
  85.         g[b].vertex = temp1;  
  86.         temp1 -> next = NULL;  
  87.     }  
  88.     else{  
  89.         temp1 ->next = g[b].vertex;  
  90.         g[b].vertex = temp1;  
  91.     }  
  92. }  
  93.   
  94. void init_graph(Graph *g){  
  95.     int i;  
  96.     for(i = 0; i <= N; i++){  
  97.         g[i].vertex = NULL;  
  98.     }  
  99. }         

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。