首页 > 其他 > 详细

CodeForces 796D

时间:2019-11-13 15:32:32      阅读:73      评论:0      收藏:0      [点我收藏+]

不能一个一个bfs,要一起bfs

技术分享图片

 

 

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 300100
using namespace std;
vector<int>G[maxn];
void insert(int be, int en) {
	G[be].push_back(en);
}
int n, m, k;
int vis[maxn];
queue<int>que;
int bfs() {
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		for (int i = 0; i < G[x].size(); i++) {
			int p = G[x][i];
			if (!vis[p]) {
				vis[p] = vis[x];
				que.push(p);
			}
		}
	}
	return 0;
}
struct Node {
	int be, en;
}cnn[maxn];
vector<int>ins;

int main() {
	int be, en;
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &be);
		if(vis[be] == 0) que.push(be);
		vis[be] = i;
	}
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &be, &en);
		insert(be, en);
		insert(en, be);
		cnn[i].be = be;
		cnn[i].en = en;
	}
	int cnt = 0;
	bfs();
	for (int i = 1; i < n; i++) {
		be = cnn[i].be;
		en = cnn[i].en;
		if (vis[be] != vis[en]) {
			ins.push_back(i);
		}
	}
	printf("%d\n", ins.size());
	for (int i = 0;i< ins.size(); i++) {
		printf("%d ", ins[i]);
	}
	printf("\n");
	return 0;
}

  

CodeForces 796D

原文:https://www.cnblogs.com/lesning/p/11849759.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!