zoj 1789 || poj 1611 The Suspects（并查集）

57 阅读 0 评论 38 点赞

我是靠谱客的博主飘逸老师，最近开发中收集的这篇文章主要介绍zoj 1789 || poj 1611 The Suspects（并查集），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

水水的并查集。

开始没想明白，就硬做了 = =。。。建了两个邻接表，每个group连接他的members，每个member连接他的groups。

然后从member 0开始搜，连接的group再搜他的members。。。DFS @ @。。搜到的标记下，最后扫下表。。。输出。

数据量不大，水过了。。

并查集想法，还是看别人的想法，惭愧，其实昨天做的那道和这题很类似的。。。为嘛没想出来呢。。。

输入的时候就合并。同一group的成员pre都改到和他同一个group最小成员的编号。同时将数目加到最小成员上。

最后输出成员0的数目即可。

DFS

#include <stdio.h> #include <stdlib.h> #include <iostream> #include <string.h> #define MAX 30010 using namespace std; typedef struct SARS{ int num; SARS *next; }SARS; SARS *group[510],*su[MAX],*node; int flag[MAX],gr[510]; void init() { memset(su,'/0',sizeof(su)); memset(gr,0,sizeof(gr)); memset(group,'/0',sizeof(group)); memset(flag,0,sizeof(flag)); } void DFS(int g) { SARS *head = group[g],*h; gr[g] = 1; while( head != NULL ) { if( !flag[head->num] ) { flag[head->num] = 1; h = su[head->num]; while( h != NULL ) { if( !gr[h->num] ) DFS( h->num ); h = h->next; } } head = head->next; } } int main() { int n,m,i,j,k,x,ans; SARS *head; while( scanf("%d%d",&n,&m) != EOF && ( n || m ) ) { init(); for(i=0; i<m; i++) { scanf("%d",&k); for(j=0; j<k; j++) { scanf("%d",&x); node = (SARS*)malloc(sizeof(SARS)); node->num = x; node->next = group[i]; group[i] = node; node = (SARS*)malloc(sizeof(SARS)); node->num = i; node->next = su[x]; su[x] = node; } } head = su[0]; flag[0] = 1; while( head != NULL ) { DFS(head->num); head = head->next; } ans = 0; for(i=0; i<n; i++) if( flag[i] == 1 ) ans++; printf("%d/n",ans); } return 0; }

并查集

#include <stdio.h> #include <stdlib.h> #include <iostream> #include <string.h> #define MAX 30010 using namespace std; int n,pre[MAX],num[MAX]; void init() { int i; for(i=0; i<n; i++) { num[i] = 1; pre[i] = i; } } int Find(int x) { while( x != pre[x] ) x = pre[x]; return x; } void Union(int x,int y) { int a = Find(x),b = Find(y); pre[x] = a; pre[y] = b; if( a == b ) return; if( a < b ) { num[a] += num[b]; pre[b] = a; } else { num[b] += num[a]; pre[a] = b; } } int main() { int m,i,j,k,y,x; while( scanf("%d%d",&n,&m) != EOF && ( n || m ) ) { init(); for(i=0; i<m; i++) { scanf("%d",&k); scanf("%d",&y); for(j=1; j<k; j++) { scanf("%d",&x); Union(x,y); } } printf("%d/n",num[0]); } return 0; }