题意：就是有n个软件0–n-1 之后每个软件安装需要提前安装其他软件。之后把依赖关系给出，当然第0个软件不依赖任何软件。最后给出q次查询，每次查询询问安装软件x需要的体现安装软件的个数，或者删除软件x需要删除软件的个数。0 0
好吧，我在赛场上第一个想到的是并查集，但WA后发现，我理解有误，之后发现这就是个模拟题，之后转用vector，但发现0 0…………继续WA，之后发现原因是我忘记了软件之间可以相互制约。 就是 安装软件2依赖于软件3，软件3依赖于软件4，那么我们就在安装软件2的时候安装上软件3和4………………之后我们再安装软件3时就不需要安装了，因为安装软件2已经安装完毕。
#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <set> #define ins(x) insert(x) #define maxs 202020 #define pb(x) push_back(x) #include <string.h> #include <bits/stdc++.h> #define mme(i,j) memset(i,j,sizeof(i)) #define lbt(x) (x&-x) #define ll long long using namespace std; vector<int>depend[105]; vector<int>depended[105]; char s[23]; bool isInstall[200]; int Install(int x) { if(isInstall[x]) return 0; isInstall[x]=1; int ans=0; for(int i=depend[x].size()-1;i>=0;i--) ans+=Install(depend[x][i]); return ans+1; } int Unstall(int x) { if(!isInstall[x]) return 0; isInstall[x]=0; int ans=0; for(int i=depended[x].size()-1;i>=0;i--) ans+=Unstall(depended[x][i]); return ans+1; } int main() { int t,n,m; scanf("%d",&t); while(t--) { mme(isInstall,0); scanf("%d",&n); for(int i=0;i<=n;i++) { depend[i].clear(); depended[i].clear(); } int m,x; for(int i=1;i<n;i++) { scanf("%d",&m); while(m--) { scanf("%d",&x); depend[i].pb(x);// i 依赖 x depended[x].pb(i);// x 被 i 依赖 } } int q; scanf("%d",&q); while(q--) { scanf("%s%d",s,&x); if(s[0]=='i') { printf("%d\n",Install(x)); } else if(s[0]=='u') printf("%d\n",Unstall(x)); } } return 0; }