#P18318. Majority Graph
Majority Graph
Majority Graph
给定长度为 的数组 。
按照下面的规则构造一个有 个顶点的无向图 ,顶点编号为 :对于每一对满足 的下标,当且仅当子数组
存在一个多数元素时,在顶点 之间连一条边。
长度为 的数组存在多数元素,指存在某个值,其出现次数严格大于 。
求图 的连通分量数量。
输入格式
第一行包含整数 ,表示测试用例数。
每组测试用例包含两行:
- 第一行包含整数 ,表示数组长度,也是图的顶点数。
- 第二行包含 个整数 。
输出格式
对于每组测试用例,输出一行,包含图 的连通分量数量。
数据范围
- ;
- ;
- ;
- 全部测试用例的 之和不超过 。
注意,本题的 上限高于通常的数组题。
样例
输入
4
4
1 2 1 2
5
1 2 3 2 1
2
1 1
3
2 2 1
输出
2
4
1
1
说明
第一组测试中,满足条件的下标对只有 和 。子数组 的多数元素是1,子数组 的多数元素是2,因此图有2个连通分量。
第二组测试中,只有一条边 ,因此图有4个连通分量。