1242. Werewolf（ｄｆｓ）

简单ｄｆｓ　往孩子方向搜一遍　父母方向搜一遍　输入还搞什么字符串。。
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<vector>
 7 using namespace std;
 8 vector<int>fa[1010];
 9 vector<int>ch[1010];
10 int u,v,q[1010];
11 int w[1010],vis1[1010],vis2[1010],o;
12 void dfs1(int u)
13 {
14     int i;
15     for(i = 0 ; i < (int)fa[u].size() ; i++)
16     {
17         int v = fa[u][i];
18         if(!vis1[v])
19         {
20             vis1[v] = 1;
21             dfs1(v);
22         }
23     }
24 }
25 void dfs2(int u)
26 {
27     int i;
28     for(i = 0 ; i < (int)ch[u].size() ; i++)
29     {
30         int v = ch[u][i];
31         if(!vis2[v])
32         {
33             vis2[v] = 1;
34             dfs2(v);
35         }
36     }
37 }
38 int main()
39 {
40     int i,j,n;
41     char s1[20],s2[20];
42     scanf("%d",&n);
43     while(cin>>s1)
44     {
45         if(strcmp(s1,"BLOOD")==0)
46         break;
47         cin>>s2;
48         u = atoi(s1);
49         v = atoi(s2);
50         fa[u].push_back(v);
51         ch[v].push_back(u);
52     }
53     int g = 0;
54     while(scanf("%d",&j)!=EOF)
55     {
56         g++;
57         q[g] = j;
58     }
59     for(i = 1; i <= g ; i++)
60     {
61         if(!vis1[q[i]])
62         {
63             vis1[q[i]] = 1;
64             dfs1(q[i]);
65         }
66     }
67     for(i = 1; i <= g ; i++)
68     {
69         if(!vis2[q[i]])
70         {
71             vis2[q[i]] = 1;
72             dfs2(q[i]);
73         }
74     }
75     for(i = 1; i <= n ;i++)
76     if(!vis2[i]&&!vis1[i])
77     {
78         o++;
79         w[o] = i;
80     }
81     if(!o)
82     printf("0
");
83     else
84     {
85         for(i = 1; i < o ; i++)
86         printf("%d ",w[i]);
87         printf("%d
",w[o]);
88     }
89     return 0;
90 }
View Code