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 1990 MooFest 树状数组
题意就是有N头牛,每头牛都有一个坐标和声调值(x, v),两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值,现在要任意两头牛之间都相互通讯一次,求总共需要花费多少能量?
52 0
|
人机交互
POJ-2524,Ubiquitous Religions(并查集模板题)
POJ-2524,Ubiquitous Religions(并查集模板题)
POJ-2253,Frogger(最短路问题)
POJ-2253,Frogger(最短路问题)
|
人工智能 网络架构
|
人工智能 C++

热门文章

最新文章