9.6腾讯笔试第二题 求助大佬
我也是用的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;
}
