Fork me on GitHub

PAT(甲级)渡劫(五)-The Largest Generation (25)


PAT(甲级)渡劫(五)-The Largest Generation (25)

题目大意:

就是统计一下每层的节点数,输出节点数最多的个数和对应的层数即可。

算法思想:

采用层次遍历

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 105;
const int inf = 1e9;
vector<int> graph[maxn]; // 邻接表
bool vis[maxn]; // 访问标记数组

int lev = 1; // 记录层次数
int sum = 0; // 记录每层的结点个数
int ans = 1; //

void BFS(int s){
queue<int> q;
q.push(s); // 将根结点入队列
vis[s] = true;
int tail;
int last = s; // 记录队列的最后一个结点
int cnt = 1;
while(q.empty() == false){
int k = q.front();
q.pop();
int n = graph[k].size();
for(int i = 0 ; i < n ; i++){
if(!vis[graph[k][i]]){
q.push(graph[k][i]);
vis[graph[k][i]] = true;
tail = graph[k][i]; // 记录该层最后一个结点的编号
sum++; // 结点个数加1
}
}
if(k == last){ // 若该层遍历完毕
last = tail; // 更新队列的最后一个结点
cnt++; // 层数加一
if(ans < sum){ // 求每层中最多的结点个数,并记录他的层数
ans = sum;
lev = cnt;
}
sum = 0; // 每层结点个数重新计数
}
}
}

int main(){
int n,m,k,t;
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i = 0 ; i < m ; i++){
int id;
cin>>id>>k;
for(int j = 0 ; j < k ; j++){
cin>>t;
graph[id].push_back(t);
graph[t].push_back(id);
}
}
BFS(1);
printf("%d %d\n",ans,lev);

return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%