好贷网好贷款

nyoj 20

发布时间:2016-12-4 1:48:01 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"nyoj 20",主要涉及到nyoj 20方面的内容,对于nyoj 20感兴趣的同学可以参考一下。

吝啬的国度 时间限制: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 该题就是将图用邻接表建立起来后,直接进行深搜一遍就完事! 比较简单, 直接附代码: [cpp] view plaincopyprint?   #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;      }  }         

上一篇:hdu 2844 Coins
下一篇:计算机核心期刊新排名(八大学报)

相关文章

关键词: nyoj 20

相关评论