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;
}
相关文章
|
人工智能 算法 BI
poj 2192 Zipper
题目链接:http://poj.org/problem?id=2192 Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 18658   Accepted: 6651 Description Given ...
976 0
|
测试技术
POJ 1001
此题用最朴素的思路实现即可,需模拟加法器,乘法器,最烦人的地方是特殊情形,如末位是小数点(12.^2=144,取小数点),整数末位是0(100^2=10000),0次幂,测试用例可能超出题目中说的范围,可能包含0次幂(100.0^0=0, 0.10^1=0.1)。
752 0
|
JavaScript
|
机器学习/深度学习
|
存储
大数加法-poj-1503
poj-1503-Integer Inquiry Description One of the first users of BIT's new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking vari
1118 0
|
算法 存储
POJ 1014 Dividing 解答
题目详见http://poj.org/problem?id=1014 看到这道题第一反应便知道它是一道类似背包问题的题,  解法我自然而然得从背包问题的解法入手,  网上查了查,  背包问题的基本题型是01背包, 即每种...
1043 0