网站源码运行,wordpress phpmyadmin插件,网站建设注册什么公司好,合肥网站建设王道下拉??正题
题目链接#xff1a; http://poj.org/problem?id1611 大意
有n个人#xff0c;m个组#xff0c;有一个流感嫌犯#xff0c;流感嫌犯会将所在的组的所有人变成流感嫌犯#xff0c;求流感嫌犯的数量。 解题思路
并查集将各个组合并#xff0c;然后看看那些人是和…正题
题目链接 http://poj.org/problem?id1611 大意
有n个人m个组有一个流感嫌犯流感嫌犯会将所在的组的所有人变成流感嫌犯求流感嫌犯的数量。 解题思路
并查集将各个组合并然后看看那些人是和嫌犯一个组的就好了。 代码
#includecstdio
#includealgorithm
using namespace std;
int lt[30001],x,k,n,m,s,head;
int father(int x)
{if (lt[x]!x) lt[x]father(lt[x]);return lt[x];
}//寻找祖先
void unionn(int x,int y)
{int fafather(x);int fbfather(y);if (fafb) lt[fb]fa;else lt[fa]fb;//取最小的当祖先
}//链接两点
int main()
{while (true){scanf(%d%d,n,m);if (n0) break;for (int i0;in;i) lt[i]i;for (int i1;im;i){scanf(%d,k);if (k1) scanf(%d,head);for (int j2;jk;j){scanf(%d,x);unionn(x,head);//连接}}s0;for (int i0;in;i) if (father(i)0) s;//统计数量printf(%d\n,s);}
}
