7-3 六度空间 (30 分) 广搜

    xiaoxiao2022-07-05  192

    #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int m,n; const int maxn=10001; vector<int>v[maxn]; int level[maxn]; int visited[maxn]; queue<int>q; void bfs(int i) { memset(level,0,sizeof(level)); memset(visited,0,sizeof(visited)); level[i]=1; q.push(i); visited[i]=1; while(!q.empty()) { int top=q.front(); q.pop(); for(int j=0; j<v[top].size(); ++j) { if(visited[v[top][j]]==0)//只要没有入过队 { q.push(v[top][j]); visited[v[top][j]]=1; level[v[top][j]]=level[top]+1; } } } int cnt=0; for(int j=1; j<=n; ++j) { if(level[j]<=7&&level[j]!=0) { cnt++; } } printf("%d: %.2f%%\n",i,1.0*100*cnt/n); } int main() { cin>>n>>m; for(int i=0; i<m; ++i) { int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } for(int i=1; i<=n; ++i) //对每一个顶点进行广度遍历, { bfs(i); } return 0; }

     

    最新回复(0)