http://poj.org/problem?id=1611
import java.util.*;
public class Main
{
Scanner scan=new Scanner(System.in);
int[] arr=new int[30010],num=new int[30010];
public static void main(String[] args)
{
new Main().run();
}
int find(int x)
{
if(arr[x]!=x)
arr[x]=find(arr[x]);
return arr[x];
}
void merge(int a,int b)
{
int fa=find(a);
int fb=find(b);
if(fa==fb)
return;
arr[fa]=fb;
num[fb]+=num[fa];
}
void init(int n)
{
for(int i=0;i<n;i++)
{
arr[i]=i;
num[i]=1;
}
}
void run()
{
while(true)
{
int n=scan.nextInt();
int m=scan.nextInt();
if(n==0)
break;
init(n);
while(m-->0)//==for(int i=1;i<=m;i++)
{
int k=scan.nextInt()-1;//注意是从0开始
int a=scan.nextInt();
while(k-->0)
{
merge(a,scan.nextInt());
}
}
System.out.println(num[find(0)]);
}
}
}
分享到:
相关推荐
poj 1611 The Suspects 代码 并查集的应用
poj 1611 The Suspects.md
【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...
【标题】"POJ1027 - The Same Game"是一个经典的编程竞赛题目,源自北京大学的在线编程平台POJ(Problem Online Judge)。该题目主要考察的是动态规划和矩阵链乘法的知识,要求参赛者编写程序解决一个具有策略性的...
标题中的“POJ 1054 The Troublesome Frog”是一个编程竞赛题目,来源于“Programming Online Judge”(POJ)平台。这个平台是程序员们练习算法和编程技能的地方,通常涉及各种数据结构和算法的问题。题目...
poj 3191 The Moronic Cowmpouter.md
poj 3260 The Fewest Coins.md
poj 1989 The Cow Lineup.md
poj 3901 The Computer Game.md
北大POJ1163-The Triangle
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
【标题】"POJ1163 - The Triangle" 是北京大学在线编程平台POJ上的一道算法题目。这道题目通常被归类为计算机科学与信息技术领域的算法问题,特别是涉及数据结构和动态规划的子领域。 【描述】该题目的解题报告详细...
有多个任务一起开始执行,每个任务的时间不同,输出前n次的任务结果
标题“POJ2151-Check the difficulty of problems”是指一个编程竞赛题目,来源于北京大学的在线判题系统POJ(PKU Online Judge)。这个题目要求参赛者编写程序来评估问题的难度。描述中的“解题报告+AC代码”表明...
《POJ2983-Is the Information Reliable:解析差分约束与优化Bellman算法》 北京大学在线编程平台上的POJ2983题目——"Is the Information Reliable",是一道涉及差分约束系统(Differential Constraint System)与...
北大POJ3267-The Cow Lexicon
【标签】"POJ 3982 The Fibonacci sequence"是这个编程问题的标识,便于搜索和分类。POJ平台上的每个题目都有唯一的标签,方便用户查找和回顾。 斐波那契序列是计算机科学中一个基础而重要的概念,它的定义如下:...
【标题】"POJ2635 - The Embarrassed Cryptographer" 是一道来源于北京大学在线判题系统POJ(Problem Set)的编程题目。这道题目的主要目标是解决一个与密码学相关的问题,通常这类问题会涉及到算法设计、字符串处理...
《POJ2635-The Embarrassed Cryptographer:测试数据解析与算法探讨》 POJ2635,这是一个源自NCPC(全国大学生程序设计竞赛)2005年问题D的编程挑战,名为“尴尬的密码学家”。在本文中,我们将深入探讨这个问题的...
【Poj 3650 The Seven Percent Solution】是一道源于ACM(国际大学生程序设计竞赛)的字符串处理问题。该题目要求编写一个程序,对输入的字符串进行特定的字符替换,将某些特定字符替换为它们后面跟着空格的ASCII码...