three version are provided.
disjoint set, linked list version with weighted-union heuristic, rooted tree version with rank by union and path compression, and a minor but substantial optimization for path compression version FindSet to avoid redundancy so to be more efficient. (31 ms to 15 ms)
reference:
1. Thomas H. Cormen, Introduction to Algorithms
2. Disjoint-set Data Structures By vlad_D– TopCoder Member https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/
in linked list version with weighted-union heuristic, with a extra tail member in struct myNode to speedup union, find is O(1), simply the p->head, so I remove find() and just used p->head as the find function.
(one main point) every time a list become no longer list, change its head’s num from 1 to 0, thus facilitate the afterwards count process – all node’s num is simply 0 except the ones as the head of linked lists. – similar process in the rooted tree version.
// linked list version with weighted-union heuristic, 15 ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXSIZE 1005
struct myNode {
int num;
myNode *head;
myNode *next;
myNode *tail;
};
void MergeSet(myNode *p1, myNode *p2) {
p1=p1->head, p2=p2->head;
if(p1->num<p2->num) { std::swap(p1,p2); }
p1->num+=p2->num, p2->num=0;
p1->tail->next=p2, p1->tail=p2->tail;
for(;p2;p2=p2->next) { p2->head=p1; }
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T, n,m,u,v,i,cnt;
myNode cities[MAXSIZE], *p,*pend, *q;
while(scanf("%d%d",&n,&m)==2 && n>0) {
for(p=&cities[1],pend=p+n;p!=pend;++p) { p->num=1; p->head=p; p->next=0; p->tail=p; }
for(i=0;i<m;++i) {
scanf("%d%d",&u,&v);
if(cities[u].head!=cities[v].head) { MergeSet(&cities[u],&cities[v]); }
}
for(cnt=-1, p=&cities[1],pend=p+n;p!=pend;++p) {
if(p->num>0) ++cnt;
}
printf("%d\n",cnt);
}
return 0;
}// rooted tree version, with rank by union and path compression, 31 ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXSIZE 1005
struct myNode {
int rank;
myNode *parent;
};
myNode* FindSet(myNode *p1) {
if(p1->parent==p1) return p1;
return p1->parent=FindSet(p1->parent);
}
void Link(myNode *p1, myNode *p2) {
if(p1->rank<p2->rank) std::swap(p1,p2);
p2->parent=p1;
p2->rank=0;
if(p1->rank==p2->rank) ++p1->rank;
}
void MergeSet(myNode *p1, myNode *p2) {
Link(FindSet(p1),FindSet(p2));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T, n,m,u,v,i,cnt;
myNode cities[MAXSIZE], *p,*pend, *q;
while(scanf("%d%d",&n,&m)==2 && n>0) {
for(p=&cities[1],pend=p+n;p!=pend;++p) { p->rank=1; p->parent=p; }
for(i=0;i<m;++i) {
scanf("%d%d",&u,&v);
if(FindSet(&cities[u])!=FindSet(&cities[v]))
MergeSet(&cities[u],&cities[v]);
}
for(cnt=-1, p=&cities[1],pend=p+n;p!=pend;++p) {
if(p->rank>0) ++cnt;
}
printf("%d\n",cnt);
}
return 0;
}note that in version 2, the path compression FindSet is a two pass recursive function, first pass up to find parent and then pass down return it to update p->parent, thus achieve path compression.
(another main point) But, note that, even when p->parent is the representative, there is no need to update p->parent, FindSet still obliviously call FindSet(p->parent) and assign it to p->parent, which does nothing useful. We can remove this redundancy by a simple modification, in FindSet, replace
if(p1->parent==p1) return p1;with
if(p1->parent==p1->parent->parent) return p1->parent;// almost same with version 2, with the optimization just mentioned, 15 ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXSIZE 1005
struct myNode {
int rank;
myNode *parent;
};
myNode* FindSet(myNode *p1) {
if(p1->parent==p1->parent->parent) return p1->parent;
return p1->parent=FindSet(p1->parent);
}
void Link(myNode *p1, myNode *p2) {
if(p1->rank<p2->rank) std::swap(p1,p2);
p2->parent=p1;
p2->rank=0;
if(p1->rank==p2->rank) ++p1->rank;
}
void MergeSet(myNode *p1, myNode *p2) {
Link(FindSet(p1),FindSet(p2));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T, n,m,u,v,i,cnt;
myNode cities[MAXSIZE], *p,*pend, *q;
while(scanf("%d%d",&n,&m)==2 && n>0) {
for(p=&cities[1],pend=p+n;p!=pend;++p) { p->rank=1; p->parent=p; }
for(i=0;i<m;++i) {
scanf("%d%d",&u,&v);
if(FindSet(&cities[u])!=FindSet(&cities[v]))
MergeSet(&cities[u],&cities[v]);
}
for(cnt=-1, p=&cities[1],pend=p+n;p!=pend;++p) {
if(p->rank>0) ++cnt;
}
printf("%d\n",cnt);
}
return 0;
}版权声明：本文为博主原创文章，未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.