我也是用的bfs方法来做,只不过我是用map来记录每个人他属于的小团队。然后用队列做bfs,明明样例运行结果正确,但是提交是0%。有大佬知道是怎么回事吗,当时我花了一个小时就看这题😫
#include <iostream> #include <stack> #include <queue> #include <vector> #include <map> #include <set> #include <string> #include <sstream> #include <stdlib.h> #include<cstring> #include<algorithm> using namespace std; //维护一个map,key是人的编号,value是他所属的团队的编号。 //从0开始bfs。并且设置visited数组标记已经访问过的团队。 queue<int> q;//用来放人的 map<int, vector<int> > person2team;//一个人可能属于很多个团队 vector<vector<int> > teams; vector<int> team; int main() { int n, m; cin>>n>>m; for(int i=0;i<m;i++) { int x; cin>>x; team.clear(); while(x--) { int person; cin>>person; team.push_back(person); person2team[person].push_back(i); } teams.push_back(team); } bool visited[m+1]; for(int i=0;i<m;i++){ visited[i]=false; } bool person_visited[n+1]; for(int i=0;i<n;i++){ person_visited[i]=false; } int cnt=0; q.push(0); while(!q.empty()) { int cur=q.front(); q.pop(); cnt++; person_visited[cur]=true; vector<int> ts=person2team[cur]; for(int i=0;i<ts.size();i++) { int t=ts[i];//当前需要考虑的团队编号 if(visited[t]){//这个团队的人都通知过了 continue; } //这个团队的人没通知过,把这些人都加进队列里 for(int j=0;j<teams[t].size();j++){ int person=teams[t][j]; if(person_visited[person]==false) q.push(person); } visited[t]=true; } } cout<<cnt<<endl; }
全部评论
(3) 回帖