题目

PAT 甲级 1094 The Largest Generation (25分) DFS BFS

思路

DFS

BFS

易错点

1 DFS中，book[level]++在递归退出条件之前，因为每次进入dfs都是一个结点，所以要统计 2 BFS中，最开始入队列的是1，因为题目已知1号结点为根结点，bfs要从根结点开始

题解

DFS

#include <iostream> #include <vector> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 110; vector<int> vs[maxn]; int book[maxn],maxl; void dfs(int v,int level){ book[level]++; //易错点，只要有结点进入dfs，对应层就加1 maxl = max(maxl,level); if(vs[v].size()==0)return; for(int i=0;i<vs[v].size();i++){ dfs(vs[v][i],level+1); } } int main(int argc,char * argv[]){ int n,m,id,k,cid; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&id,&k); for(int j=0;j<k;j++){ scanf("%d",&cid); vs[id].push_back(cid); } } // 2 dfs dfs(1,1); // 3 找到结点数最多的层 int maxpi=0; //人数最多的群 for(int i=1;i<=maxl;i++){ if(book[i]>book[maxpi]){ maxpi = i; } } printf("%d %d",book[maxpi],maxpi); return 0; }

BFS

#include <iostream> #include <vector> #include <cstring> #include <unordered_map> #include <stack> #include <queue> #include <algorithm> #include <cmath> using namespace std; const int maxn = 110; vector<int> vs[maxn]; // book 记录每层节点总数，level 记录结点在哪一层 // maxpi 记录最多人数层号，maxp 记录最多人数 int book[maxn],maxpi,maxp,level[maxn]; void bfs(){ queue<int> q; q.push(1); level[1]=1; while(!q.empty()){ int now = q.front(); q.pop(); book[level[now]]++; if(book[level[now]]>maxp){ maxp = book[level[now]]; maxpi = level[now]; } for(int i=0;i<vs[now].size();i++){ level[vs[now][i]]=level[now]+1; q.push(vs[now][i]); } } } int main(int argc,char * argv[]){ int n,m,id,k,cid; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&id,&k); for(int j=0;j<k;j++){ scanf("%d",&cid); vs[id].push_back(cid); } } // 2 dfs bfs(); printf("%d %d",maxp,maxpi); return 0; }