吝啬的国度简单的图搜索

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <stdlib.h>
 5 int pre[100005];
 6 typedef struct edge
 7 {
 8     int v;
 9     struct edge *next;
10 }edge;
11 struct height{
12     int num;
13     struct edge *next;
14 }head[200010];
15 
16 void add(int a,int b)//加边
17 {
18     edge *ss=(edge *)malloc(sizeof(edge));
19     ss->v=b;
20     ss->next=head[a].next;
21     head[a].next=ss;
22 }
23 
24 void dfs(int cur)   //搜索
25 {
26     edge *s;
27     for(s=head[cur].next;s!=NULL;s=s->next)
28     {
29         if(pre[s->v])//标记搜索过了，并且找到当前的v的前驱；
30             continue;
31         pre[s->v]=cur;
32         dfs(s->v);
33     }
34 }
35     
36 int main()
37 {
38     int m,n,s,a,b;
39     scanf("%d",&m);
40     while(m--)
41     {
42         memset(head,NULL,sizeof(head));
43         memset(pre,0,sizeof(pre));
44         scanf("%d%d",&n,&s);
45         for(int i=1;i<n;i++)
46         {
47             scanf("%d%d",&a,&b);
48             add(a,b);   add(b,a);
49         }
50         pre[s]=-1;
51         dfs(s);
52         for(int i=1;i<n;i++)
53             printf("%d ",pre[i]);
54         printf("%d
",pre[n]);
55     }
56     return 0;
57 }
58
View Code
吝啬的国度 简单的图搜索

吝啬的国度简单的图搜索
