唯一的WA
是把0的父亲当成祖先
father[x]和getfather(x)差别巨大啊
Program p1611;
const
maxn=30010;
maxm=500;
var
n,m,i,j,k,p1,p2,ans,f0:longint;
father:array[0..maxn] of longint;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
procedure union(x,y:longint);
begin
if getfather(x)<>getfather(y) then
father[father[x]]:=father[father[y]];
end;
begin
read(n,m);
while (n+m>0) do
begin
for i:=0 to n-1 do father[i]:=i;
for i:=1 to m do
begin
read(k);
if k>0 then read(p1);
if k>1 then
for j:=2 to k do
begin
read(p2);
union(p1,p2);
end;
end;
ans:=1;
f0:=getfather(0);
for i:=1 to n-1 do if getfather(i)=f0 then inc(ans);
writeln(ans);
read(n,m);
end;
end.
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
poj 1611 The Suspects 代码 并查集的应用
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
并查集基础 acm 算法 poj oi 并查集基础.ppt
POJ1089 并查集可以解决 并查集加路径压缩
这份代码用C++实现了经典算法并查集,来源于poj题目1182
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
poj 食物链代码.带权并查集,关键是找到其中的一些关系式.
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
poj题目分类,适合acmer学习研究 ...9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流算法: 1.送分题 2.构造 3.高精度 4.几何 5.排序 6.日期/时间处理 (这类题目相当多的) 7.数学方法
//http://poj.org/problem?id=1611 #include using namespace std; const int maxn = 30010; int f[maxn],num[maxn],n,m; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { while(cin...
利用并查集判断环路,以及快速排序计算最小生成树
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 ...poj2832 并查集边的计算 sgu218 hcraft 二分图匹配验证 二分答案
主流算法: 1.搜索 //回溯 2.DP(动态规划) 3.贪心 4.图论 //Dijkstra、最小生成树、网络...9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、回溯、遍历 3、历法 4、 枚举 5、 数据结构的典型算法 6、 动态规划
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
2.最小生成树(先写个prim,kruscal要用并查集,不好写) 3.大数(高精度)加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) ...
并查集 堆 哈希表 DFS BFS 快速幂 背包问题 区间DP 区间问题 绝对值不等式 DP课 寒假每日一题 基础班 提高班 POJ 大二 2019 新生赛 蓝桥杯模拟 蓝桥杯学习 bfs 大数 dfs/抽象dfs 逻辑 测试 栈/递归 清华oj入门
7.3 并查集 151 7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割...
2.4.4 并查集 2.5 它们其实都是“图” 2.5.1 图是什么 2.5.2 图的表示 2.5.3 图的搜索 2.5.4 最短路问题 2.5.5 最小生成树 2.5.6 应用问题 2.6 数学问题的解题窍门 2.6.1 辗转相除法 2.6.2 有关素数的基础算法 2.6.3...