By Jalan
文章目录
**By Jalan**知识工具需求数学数据结构和算法语言
题干输入条件输出条件例子例1输入输出
题解第一次思路预期时间复杂度编写用时代码CPP运行用时
结尾
知识工具需求
数学
数据结构和算法
并查集
语言
题干
假设一张照片里的鸟在同一颗树上.问树和鸟的总数和鸟和鸟是否同树.
输入条件
N<=1000照片数 k Bi照片里的鸟数和鸟号4位 q问题数 b1 b2两只鸟
输出条件
树数 鸟数 这个q下的两只鸟在不在同一颗树
例子
例1
输入
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出
2 10
Yes
No
题解
第一次
思路
输入,在输入同时进行union.使用一个map来统计多少鸟.使用一个数组total把所有鸟的号存起来使用另一个map统计多少树按询问找两者的root一致同树Yes,不一致No
预期时间复杂度
编写用时
25分钟
代码
CPP
#include <bits/stdc++.h>
#include <stdio.h>
#include <vector>
using namespace std
;
void initiate(vector
<int> &parent
)
{
for (int i
= 0; i
< parent
.size(); i
++)
{
parent
[i
] = i
;
}
}
int findRoot(int vertex
, vector
<int> &parent
)
{
int originVertex
= vertex
;
while (parent
[vertex
] != vertex
)
{
vertex
= parent
[vertex
];
}
while (parent
[originVertex
] != originVertex
)
{
int nowVertex
= originVertex
;
parent
[originVertex
] = vertex
;
originVertex
= parent
[nowVertex
];
}
return vertex
;
}
int unionVertex(int va
, int vb
, vector
<int> &parent
)
{
int ar
= findRoot(va
, parent
);
int br
= findRoot(vb
, parent
);
parent
[ar
] = br
;
return 1;
}
int main(int argc
, char const *argv
[])
{
vector
<int> parent(10001);
initiate(parent
);
int n
;
scanf("%d", &n
);
unordered_map
<int, int> birdsMap
;
vector
<int> total
;
for (int i
= 0; i
< n
; i
++)
{
int lineCounter
;
scanf("%d", &lineCounter
);
vector
<int> lineBirds
;
for (int j
= 0, temp
; j
< lineCounter
; j
++)
{
scanf("%d", &temp
);
lineBirds
.push_back(temp
);
}
for (int j
= 1; j
< lineCounter
; j
++)
{
unionVertex(lineBirds
[0], lineBirds
[j
], parent
);
}
for (int j
= 0; j
< lineCounter
; j
++)
{
birdsMap
[lineBirds
[j
]]++;
total
.push_back(lineBirds
[j
]);
}
}
unordered_map
<int, int> treeMap
;
for (int i
= 0; i
< total
.size(); i
++)
{
treeMap
[findRoot(total
[i
], parent
)]++;
}
printf("%d %d\n", treeMap
.size(), birdsMap
.size());
int q
;
scanf("%d", &q
);
for (int i
= 0; i
< q
; i
++)
{
int a
, b
;
scanf("%d%d", &a
, &b
);
if (findRoot(a
, parent
) == findRoot(b
, parent
))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
运行用时
结尾
看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀@.@ 也欢迎关注我的账号呀,接下来两个月我应该会按这个格式更新所有的PTA甲级题目
**开心code每一天**
