#include<stdio.h>#include<string.h>#include<algorithm>#include<vector>#include<iostream>#include<string>using namespace std;vector<int>v[103];vector<int>u[103];bool num[100003];int in(int x){ int ans=0; if(num[x]) return 0; num[x]=true; for(int i=0;i<v[x].size();i++) { ans+=in(v[x][i]); } return ans+1;}int un(int x){ int ans=0; if(!num[x]) return 0; num[x]=false; for(int i=0;i<u[x].size();i++) { ans+=un(u[x][i]); } return ans+1;}int main(){ int T; cin>>T; while(T--) { int n,x,t; memset(num,false,sizeof(num)); cin>>n; for(int i=0; i<n; i++) { v[i].clear(); u[i].clear(); } for(int i=1; i<n; i++) { cin>>t; for(int j=1; j<=t; j++) { cin>>x; v[i].push_back(x); u[x].push_back(i); } } int q; cin>>q; while(q--) { string s; int z; cin>>s>>z; int ans=(s=="install")?in(z):un(z); cout<<ans<<endl; } }}
| Distinct Package Manager | ||||||
|
||||||
| Description | ||||||
|
On Linux or OSX, we can install software by package manager. For example, apt-get in Ubuntu/Debian, yum in Fedora/CentOS and brew in OSX. All of them are great software-package manager. You determined to design your own software-package manager. The inevitable thing is you should solve dependences of these software-packages. • If package A depends package B, you should install package B before installing package A. • If you want to uninstall package B, then you must uninstall package A. Now, you already know all the dependences of all these software-packages. You can assume that 0-package don’t depend any other package. And all dependence-relationship won’t form a circle. Of course, no package depend itself. Your uses want to know how many packages’ install state will be changed when installing or uninstalling a package. NOTE: Install an installed package and uninstall an uninstalled package won’t change any packages’ state. |
||||||
| Input | ||||||
| There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. The first line of each test cases contains an integer n(1<=n<=100), indicating the number of software-packages. For each software-package(except 0-package) contains two lines, the first line contains an integer mi, indicating the number of dependences of i-package. The next mi integers indicating the serial numbers of dependences. The next line contains an integer q(1<=q<=200), indicating the number of queries. Each of the next q liens contains a string s and an integer k, indicating the action and serial number of software-package. s must be one of "install" and "uninstall". |
||||||
| Output | ||||||
| For each query, output a line contains the number of changed packages. | ||||||
| Sample Output | ||||||
1 |
||||||
| Hint | ||||||
22 |
||||||
| Source | ||||||
| "尚学堂杯"哈尔滨理工大学第七届程序设计竞赛 |
思路就是用两个动态数组存储她们的祖先和字辈。利用递归去查找就好了。