当前位置: 代码迷 >> 综合 >> PAT 甲级 1076 PAT Ranking 个人错误总结
  详细解决方案

PAT 甲级 1076 PAT Ranking 个人错误总结

热度:39   发布时间:2024-02-13 09:28:35.0

用dfs会超时,27分,用bfs过了。

#include<bits/stdc++.h>
using namespace std;
vector<int> user[1001];
int flag[1001];
int l;
int cnt;
void dfs(int root,int h){if(flag[root]==10000)cnt++;flag[root]=h;for(int i=0;i<user[root].size();i++){if(flag[user[root][i]]>h&&h+1<=l)dfs(user[root][i],h+1);}
}
bool visit[1001];
int h[1001];
void bfs(int root){queue<int>q;q.push(root);visit[root]=true;h[root]=0;while(q.size()){int temp=q.front();q.pop();if(h[temp]>l)return;cnt++;for(int i=0;i<user[temp].size();i++){if(visit[user[temp][i]]==false){q.push(user[temp][i]);visit[user[temp][i]]=true;h[user[temp][i]]=h[temp]+1;}}}
}
int main(){int n;scanf("%d %d",&n,&l);int temp,m;for(int i=1;i<=n;i++){scanf("%d",&m);for(int j=0;j<m;j++){scanf("%d",&temp);user[temp].push_back(i);}}int k;scanf("%d",&k);for(int i=0;i<k;i++){cnt=0;fill(visit,visit+1001,false);scanf("%d",&temp);bfs(temp);printf("%d\n",cnt-1);}return 0;
}
  相关解决方案