欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1118 Birds in Forest (25分)

程序员文章站 2022-06-04 08:22:38
...

1118 Birds in Forest (25分)
每张图片有若干只鸟。对于两张图片,如果它们有相同编号的鸟,则说明这两张图片来自同一棵树。将各图片视为结点,各图片通过相同编号的鸟联系起来,所以可以用dfs或者bfs来进行遍历。注意,除了设置picVisited来判断某张图片是否访问过,还需要设置birdVisited来判断某只鸟是否已经访问过(否则超时)。

BFS:

#include<cstdio>
#include<unordered_set>
#include<algorithm>
#include<queue>
using namespace std;
int picNum, queryNum, treeNum, birdNum = 0;
unordered_set<int> bird[10001];	//记录某只鸟属于哪些图片,注意鸟的编号1~10000
unordered_set<int> picture[10000];	//记录某张图片有哪些鸟
int pictureSource[10000];	//记录某张图片属于哪棵树
bool picVisited[10000];	//记录某张图是否访问过
bool birdRecorded[10001];	//记录某只鸟是否已经被记录
bool birdVisited[10001];	//记录某只鸟是否访问过
int treeId = 0;

int main() {
	scanf("%d", &picNum);
	for (int i = 0;i < picNum;i++) {
		int n;
		scanf("%d", &n);
		for (int j = 0;j < n;j++) {
			int temp;
			scanf("%d", &temp);
			if (!birdRecorded[temp]) {
				birdNum++;
				birdRecorded[temp] = true;
			}
			bird[temp].insert(i);
			picture[i].insert(temp);
		}
	}

	for (int i = 0;i < picNum;i++) {
		if (!picVisited[i]) {
			picVisited[i] = true;
			queue<int> q;
			q.push(i);
			while (!q.empty()) {
				int curPic = q.front();
				q.pop();
				pictureSource[curPic] = treeId;
				for (auto it1 = picture[curPic].begin(); it1 != picture[curPic].end(); it1++) {
					int birdId = *it1;
					if (!birdVisited[birdId]) {
						birdVisited[birdId] = true;
						for (auto it2 = bird[birdId].begin(); it2 != bird[birdId].end(); it2++) {
							if (!picVisited[*it2]) {
								picVisited[*it2] = true;
								q.push(*it2);
							}
						}
					}
				}
			}
			treeId++;
		}
	}

	treeNum = treeId;
	printf("%d %d\n", treeNum, birdNum);
	scanf("%d", &queryNum);
	for (int i = 0;i < queryNum;i++) {
		int b1, b2;
		scanf("%d %d", &b1, &b2);
		int picId1 = *bird[b1].begin(), picId2 = *bird[b2].begin();
		if (pictureSource[picId1] == pictureSource[picId2]) {
			printf("Yes\n");
		}
		else printf("No\n");
	}
}

DFS:

#include<cstdio>
#include<unordered_set>
#include<algorithm>
using namespace std;
int picNum, queryNum, treeNum, birdNum = 0;
unordered_set<int> bird[10001];	//记录某只鸟属于哪些图片,注意鸟的编号1~10000
unordered_set<int> picture[10000];	//记录某张图片有哪些鸟
int pictureSource[10000];	//记录某张图片属于哪棵树
bool picVisited[10000];	//记录某张图是否访问过
bool birdCounted[10001];	//记录某只鸟是否已经计数过
bool birdVisited[10001];	//记录某只鸟是否在dfs中访问过
int treeId = 0;
void dfs(int curPic) {
	picVisited[curPic] = true;
	pictureSource[curPic] = treeId;
	for (auto it1 = picture[curPic].begin(); it1 != picture[curPic].end(); it1++) {
		int birdId = *it1;
		if (!birdVisited[*it1]) {
			birdVisited[*it1] = true;
			for (auto it2 = bird[birdId].begin(); it2 != bird[birdId].end(); it2++) {
				if (!picVisited[*it2]) {
					dfs(*it2);
				}
			}
		}
	}
}
int main() {
	scanf("%d", &picNum);
	for (int i = 0;i < picNum;i++) {
		int n;
		scanf("%d", &n);
		for (int j = 0;j < n;j++) {
			int temp;
			scanf("%d", &temp);
			if (!birdCounted[temp]) {
				birdCounted[temp] = true;
				birdNum++;
			}
			bird[temp].insert(i);
			picture[i].insert(temp);
		}
	}

	for (int i = 0;i < picNum;i++) {
		if (!picVisited[i]) {
			dfs(i);
			treeId++;
		}
	}
	treeNum = treeId;
	printf("%d %d\n", treeNum, birdNum);
	scanf("%d", &queryNum);
	for (int i = 0;i < queryNum;i++) {
		int b1, b2;
		scanf("%d %d", &b1, &b2);
		int picId1 = *bird[b1].begin(), picId2 = *bird[b2].begin();
		if (pictureSource[picId1] == pictureSource[picId2]) {
			printf("Yes\n");
		}
		else printf("No\n");
	}
}