1118 Birds in Forest (25分)
程序员文章站
2022-06-04 08:22:38
...
每张图片有若干只鸟。对于两张图片,如果它们有相同编号的鸟,则说明这两张图片来自同一棵树。将各图片视为结点,各图片通过相同编号的鸟联系起来,所以可以用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");
}
}
推荐阅读
-
1118 Birds in Forest (25分) (并查集)
-
PAT 甲级 1118Birds in Forest (25分)
-
A1118 Birds in Forest [并查集]
-
1118 Birds in Forest (25分) / 并查集
-
PAT 甲级 1118(Birds in Forest)
-
PAT甲级 1118 Birds in Forest 并查集
-
1118 Birds in Forest (25分)【关于PAT中使用并查集的坑点】
-
1118 Birds in Forest (25分)
-
PAT_甲级_1118 Birds in Forest (25point(s)) (C++)【并查集】