UVA-1267, Network

這一題要有兩種DFS模式
初始和過程中
其他BJ4

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <algorithm>

 5 #include <list>

 6 #include <set>

 7 #include <vector>

 8 using namespace std;

 9 struct node_t{

10     node_t(){;}

11     node_t(const node_t& a){this->depth=a.depth; this->num=a.num;}

12     node_t(int d, int n){this->depth=d; this->num=n;}

13     int depth;

14     int num;

15     bool operator()(const node_t& a, const node_t& b)const{

16         if(a.depth != b.depth)    

17             return (a.depth < b.depth);

18         else

19             return (a.num < b.num);

20     }

21 };

22 int T, n;

23 int s, k;

24 int a, b;

25 int ans, tmp, news;

26 vector<int> depth(1005);

27 vector<list<int> > out(1005);

28 list<int>::iterator it, oend;

29 set<node_t, node_t> notyet;

30 void cover(int d, int caller, int now){

31     depth[now]=d;

32     if(out[now].size()>1 or now==s){ //internal node

33         list<int>::iterator oend=out[now].end();

34         for(list<int>::iterator it=out[now].begin() ; it!=oend ; it++){

35             if(*it != caller)    

36                 cover(d+1, now, *it);

37         }

38     }else{ //leaf

39         if(d > k){

40             notyet.insert(node_t(d, now));

41             return;

42         }

43     }

44     return;

45 }

46 void covered(int d, int caller, int now){

47     if(d > k)return;

48     if(out[now].size()>1){

49         list<int>::iterator oend=out[now].end();

50         for(list<int>::iterator it=out[now].begin() ; it!=oend ; it++){

51             if(*it != caller)    

52                 covered(d+1, now, *it);

53         }

54     }else{

55         if(d <= k){

56             notyet.erase(node_t(depth[now], now));

57             return;

58         }

59     }

60     return;

61 }

62 int main(){     

63     scanf("%d", &T);

64     while(T--){

65         scanf("%d", &n);

66         for(int i=1 ; i<=n ; ++i){

67             out[i].clear();

68         }

69         notyet.clear();

70         ans=0;

71 

72         scanf("%d%d", &s, &k);

73         for(int i=1 ; i<n ; ++i){

74             scanf("%d%d", &a, &b);

75             out[a].push_back(b);

76             out[b].push_back(a);

77         }

78 

79         cover(0, s, s);

80         while(not notyet.empty()){

81             tmp=notyet.rbegin()->num;

82             for(int zz=0 ; zz<k ; ++zz){ //go back k length  

83                 oend=out[tmp].end();

84                 for(it=out[tmp].begin() ; it!=oend ; it++){

85                     if(depth[*it] < depth[tmp]){

86                         tmp=*it;

87                         break;

88                     }

89                 }

90             }

91             ++ans; //tmp now is a sever

92             covered(0, tmp, tmp);

93         }

94 

95         printf("%d\n", ans);

96     }

97 return 0;

98 }