题意：给你一颗树，给你一个根 ，每一次摘取一个叶子节点，问你摘取有多少种组合。
解题思路：类拓扑排序。
解题代码：
1 // BEGIN CUT HERE 2 /* 3 4 */ 5 // END CUT HERE 6 #line 7 "OneEntrance.cpp" 7 #include <cstdlib> 8 #include <cctype> 9 #include <cstring> 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 #include <vector> 14 #include <string> 15 #include <iostream> 16 #include <sstream> 17 #include <map> 18 #include <set> 19 #include <queue> 20 #include <stack> 21 #include <fstream> 22 #include <numeric> 23 #include <iomanip> 24 #include <bitset> 25 #include <list> 26 #include <stdexcept> 27 #include <functional> 28 #include <utility> 29 #include <ctime> 30 using namespace std; 31 32 #define PB push_back 33 #define MP make_pair 34 35 #define REP(i,n) for(i=0;i<(n);++i) 36 #define FOR(i,l,h) for(i=(l);i<=(h);++i) 37 #define FORD(i,h,l) for(i=(h);i>=(l);--i) 38 39 typedef vector<int> VI; 40 typedef vector<string> VS; 41 typedef vector<double> VD; 42 typedef long long LL; 43 typedef pair<int,int> PII; 44 45 vector<int >mp[14]; 46 int vis[15]; 47 int ru[15]; 48 int len; 49 int ans ; 50 void dfs(int n ) 51 { 52 if(n == len+1) 53 { 54 ans ++ ; 55 return; 56 } 57 for(int tt = 0 ;tt <= len ; tt ++) 58 { 59 if(!vis[tt]&& ru[tt] == 1 ) 60 { 61 // printf("***%d ",tt); 62 int k = -1; 63 for(int i = 0 ;i < mp[tt].size();i ++) 64 { 65 if(!vis[mp[tt][i]]) 66 { 67 k = mp[tt][i]; 68 // printf("%d ",k); 69 break; 70 } 71 } 72 if(k == -1) 73 { 74 vis[tt] = 1; 75 dfs(n+1); 76 vis[tt] = 0 ; 77 continue;; 78 } 79 ru[tt]--; 80 ru[k] -- ; 81 vis[tt] = 1 ; 82 dfs(n+1); 83 ru[tt]++; 84 ru[k] ++ ; 85 vis[tt] = 0 ; 86 } 87 } 88 } 89 class OneEntrance 90 { 91 public: 92 int count(vector <int> a, vector <int> b, int s) 93 { 94 ans = 0 ; 95 memset(vis,0,sizeof(vis)); 96 len = a.size(); 97 if(len == 0) 98 return 1; 99 memset(ru,0,sizeof(ru)); 100 for(int i= 0 ;i <= len + 1;i ++) 101 mp[i].clear(); 102 for(int i = 0 ;i < len ;i ++) 103 { 104 mp[a[i]].push_back(b[i]); 105 mp[b[i]].push_back(a[i]); 106 ru[a[i]] ++ ; 107 ru[b[i]] ++ ; 108 } 109 vis[s] = 1 ; 110 dfs(1); 111 return ans ; 112 113 } 114 115 // BEGIN CUT HERE 116 public: 117 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); } 118 private: 119 template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '"' << *iter << "","; os << " }"; return os.str(); } 120 void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << " Expected: "" << Expected << '"' << endl; cerr << " Received: "" << Received << '"' << endl; } } 121 void test_case_0() { int Arr0[] = {0, 1, 2}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 2, 3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; int Arg3 = 1; verify_case(0, Arg3, count(Arg0, Arg1, Arg2)); } 122 void test_case_1() { int Arr0[] = {0, 1, 2}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 2, 3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; int Arg3 = 3; verify_case(1, Arg3, count(Arg0, Arg1, Arg2)); } 123 void test_case_2() { int Arr0[] = {0, 0, 0, 0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 2, 3, 4}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; int Arg3 = 24; verify_case(2, Arg3, count(Arg0, Arg1, Arg2)); } 124 void test_case_3() { int Arr0[] = {7, 4, 1, 0, 1, 1, 6, 0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {6, 6, 2, 5, 0, 3, 8, 4}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 4; int Arg3 = 896; verify_case(3, Arg3, count(Arg0, Arg1, Arg2)); } 125 void test_case_4() { int Arr0[] = {}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; int Arg3 = 1; verify_case(4, Arg3, count(Arg0, Arg1, Arg2)); } 126 127 // END CUT HERE 128 129 }; 130 131 // BEGIN CUT HERE 132 int main() 133 { 134 OneEntrance ___test; 135 ___test.run_test(-1); 136 return 0; 137 } 138 // END CUT HERE