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