浙大数据结构慕课课后题(06-图3 六度空间)

题目要求：

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤103，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。 

输出格式： 

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。 

输入样例: 

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10 

输出样例: 

1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00% 

题解： 

        思路如注释所示，可通过所有测试点。 

#include<bits/stdc++.h>
using namespace std;const int MAX_N = 1005; 
vector<vector<int>> sds;  //二维动态数组 
bool vis[MAX_N];int BFS(int v){int count = 1,level = 0,last = v,tail;queue<int> q;q.push(v);vis[v] = true;while(!q.empty()){int u = q.front();q.pop();for(int w : sds[u]){if(!vis[w]){vis[w] = true;q.push(w); count++;tail = w;		}	} if(u == last){level++; last = tail;}if(level == 6) break;}return count;
}int main(){int N,M;cin>>N>>M;sds.resize(N+1);           //动态设置sds数组的大小 fill(vis,vis + N + 1,false);   //初始化vis数组 for(int i = 0; i < M; i++){int u,v;cin>>u>>v;sds[u].push_back(v);sds[v].push_back(u);}	for(int i = 1; i <= N; i++){int count = BFS(i);	      //BFS函数的返回值即为符合要求的结点数目 double ans = 100.0*count/N;printf("%d: %.2f%%\n", i, ans);		fill(vis,vis+N+1,false);    //初始化vis数组 }return 0;
}

总结： 

1. vector二维数组的声名格式有两种：假设数组名为sds。

（1）如果我们提前知道了数组的大小可以这样定义：

MAX_N=1005;

vector<int> sds[MAX_N];

（2）如果不知道数组大小，又需要全局声名就要在main函数外这样定义： 

vector<vector<int>> sds;

然后在main函数里面这样确定数组大小：

int main(){

...

cin>>N;

sds.resize(N);        //resize()函数

...

}

2.在取百分号时，乘数100要写成100.0  虽然在代码中 用了一个double类型的数据来接收计算结果，但是如果写的是（*100）那么编译器会先进行整数乘法，再用浮点数来存取，精度已经损失了，测试点中有两个例子卡的就是这个地方（别问我怎么知道的@_@）。

3.此题的思路比较巧妙，用一个last变量来存储一层的最后一个元素，如果这个元素被弹出，则说明这一层已经遍历完成，从而实现对层数的控制，当层数>=6时，函数终止。

4.题目内容说完了，下面是关于dev编译器，我用的是比较老的devc++，因为看重了它的简洁，但是如果要用到一些c++11的特性，比如本题中的foreach循环会报错，要在这个地方设置一下。

找到编译器选项，加入红框里的语句即可。