POJ-1611,The Suspects(并查集

简介: POJ-1611,The Suspects(并查集

解题思路:


北大OJ上的一道经典并查集的题, 因为题目中说最初的学生0被视为嫌疑犯,所以只需要寻找根节点与0相等的即可。


程序代码:


#include<stdio.h>
int f[30001];
int getf(int v)
{
  if(f[v]==v)
    return v;
  else
  {
    f[v]=getf(f[v]);
    return f[v];
  }
}
void merge(int v,int u)
{
  int t1=getf(v);
  int t2=getf(u);
  if(t1!=t2)
    f[t2]=t1;
  return ;
}
int main()
{
  int n,m,i,j,k,x,y,sum;
  while(~scanf("%d %d",&n,&m))
  {
    if(n==0&&m==0)
      break;
    for(i=0;i<n;i++)
      f[i]=i;
    while(m--)
    {
      scanf("%d %d",&k,&x);
      for(j=1;j<k;j++)
      {
        scanf("%d",&y);
        merge(x,y);
      }
    }
    sum=1;
    for(i=1;i<n;i++)
    {
      if(getf(i)==getf(0))
        sum++;
    }
    printf("%d\n",sum);
  }
  return 0;
}
相关文章
|
人机交互
POJ-2524,Ubiquitous Religions(并查集模板题)
POJ-2524,Ubiquitous Religions(并查集模板题)
|
人工智能 网络架构
|
人工智能 C++
|
机器学习/深度学习
【OJ】贪心法 Saruman's Army POJ 3069 /acmclub 12132
题目链接:点击打开链接 /* 6 10 贪心法Saruman's Army POJ 3069 1 7 15 20 30 50 ans=3 */ #include #include using namespace std; int x[1010]; ...
863 0
|
机器学习/深度学习
【OJ】贪心法 Saruman&#39;s Army POJ 3069 /acmclub 12132
题目链接:点击打开链接 /* 6 10 贪心法Saruman's Army POJ 3069 1 7 15 20 30 50 ans=3 */ #include #include using namespace std; int x[1010]; int main(){ // freopen("贪心法 Saruman's Army poj3069.
820 0