| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
1a#include <iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
int f[30010], ju[30010];
int con[15000000];
int getparent(int k)
{
if(k == f[k]) return k;
else
{
f[k] = getparent(f[k]);
return f[k];
}
}
int main()
{
//freopen("D:\\CPPProgram\\ACM\\in.txt", "r", stdin);
int n, m;
while(1)
{
scanf("%d %d", &n, &m);
if(m == 0 && n == 0) break;
int cnt = 0;
memset(ju, 0, sizeof ju);
for(int i=0; i<n; i++)
{
f[i] = i;
}
for(int i=0; i<m; i++)
{
int num;
scanf("%d", &num);
for(int j=0; j<num; j++)
{
scanf("%d",&con[cnt]);
cnt++;
}
for(int j=cnt-num; j<cnt-1; j++)
{
int p1, p2;
p1 = getparent(con[j]);
p2 = getparent(con[j+1]);
if(p1 != p2)
{
f[p1] = p2;
}
}
}
int p = getparent(0);
int ans = 0;
for(int i=0; i<cnt; i++)
{
if(ju[con[i]] == 0)
{
ju[con[i]] = 1;
if(getparent(con[i]) == p)
ans++;
}
}
if(ju[0] == 0) ans++;
printf("%d\n", ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator