首页 > 9.6腾讯笔试第二题 求助大佬
头像
Ray00
编辑于 2020-09-06 22:47
+ 关注

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;
	
	
}











全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐