poj并查集
这两天学习了下并查集，顺便A了几题，感觉大体都是一样的，主要是对3个函数的应用，makeset(),find(),unionset().这里直接把我A的题目给出来。。。都是简单的。。。，后面的题目会继续A的。。。。
poj2524：
#include<stdio.h>
int fa[50005];
int rank[50005];
int n,m,result;
int make(int x)
{
fa[x]=x;
rank[x]=0;
}
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
void unionset(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return ;
result--;//
if(rank[x]>rank[y])
{
fa[y]=x;
}
else
{
fa[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
int i,j,t,x,y;
t=1;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==0&&n==0)
break;
for(i=1;i<=n;i++)
make(i);
result=n;
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
unionset(x,y);
}
printf("Case %d: %d\n",t++,result);
}
return 0;
}
#include<stdio.h>
int fa[50005];
int rank[50005];
int n,m,result;
int make(int x)
{
fa[x]=x;
rank[x]=0;
}
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
void unionset(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return ;
result--;//
if(rank[x]>rank[y])
{
fa[y]=x;
}
else
{
fa[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
int i,j,t,x,y;
t=1;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==0&&n==0)
break;
for(i=1;i<=n;i++)
make(i);
result=n;
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
unionset(x,y);
}
printf("Case %d: %d\n",t++,result);
}
return 0;
}
poj1703：
#include<iostream>
using namespace std;
const int Max = 100050;
int n, m;
int parent[Max], opp[Max]; // 用于记录x1个不同帮派opp[x]，若没有x的信息则初始化为opp[x] = 0。
void make_set(){
for(int x = 1; x <= n; x ++){
parent[x] = x;
opp[x] = 0;
}
}
int find_set(int x){
if(x != parent[x])
parent[x] = find_set(parent[x]);
return parent[x];
}
void union_set(int x, int y){
x = find_set(x);
y = find_set(y);
if(x == y) return;
parent[y] = x;
}
int main(){
int t, x, y;
scanf("%d", &t);
while(t --){
scanf("%d %d", &n, &m);
getchar();
make_set();
while(m --){
char c;
scanf("%c %d %d", &c, &x, &y);
getchar(); // 记得要回收回车号。
if(c == 'D'){
if(opp[x] == 0 && opp[y] == 0){ // 情况1：x，y在前面都没有信息。
opp[x] = y;
opp[y] = x;
}
else if(opp[x] == 0){ // 情况2：x在前面都没有信息，而y有。
opp[x] = y;
union_set(x, opp[y]);
}
else if(opp[y] == 0){ // 情况3：y在前面都没有信息，而x有。
opp[y] = x;
union_set(y, opp[x]);
}
else{ // 情况4：x，y在前面都有信息。
union_set(x, opp[y]);
union_set(y, opp[x]);
}
}
if(c == 'A'){ // 注意三种情况的判断依据。
if(find_set(x) == find_set(y))
printf("In the same gang.\n");
else if(find_set(x) == find_set(opp[y]))
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
}
}
}
return 0;
}
#include<iostream>
using namespace std;
const int Max = 100050;
int n, m;
int parent[Max], opp[Max]; // 用于记录x1个不同帮派opp[x]，若没有x的信息则初始化为opp[x] = 0。
void make_set(){
for(int x = 1; x <= n; x ++){
parent[x] = x;
opp[x] = 0;
}
}
int find_set(int x){
if(x != parent[x])
parent[x] = find_set(parent[x]);
return parent[x];
}
void union_set(int x, int y){
x = find_set(x);
y = find_set(y);
if(x == y) return;
parent[y] = x;
}
int main(){
int t, x, y;
scanf("%d", &t);
while(t --){
scanf("%d %d", &n, &m);
getchar();
make_set();
while(m --){
char c;
scanf("%c %d %d", &c, &x, &y);
getchar(); // 记得要回收回车号。
if(c == 'D'){
if(opp[x] == 0 && opp[y] == 0){ // 情况1：x，y在前面都没有信息。
opp[x] = y;
opp[y] = x;
}
else if(opp[x] == 0){ // 情况2：x在前面都没有信息，而y有。
opp[x] = y;
union_set(x, opp[y]);
}
else if(opp[y] == 0){ // 情况3：y在前面都没有信息，而x有。
opp[y] = x;
union_set(y, opp[x]);
}
else{ // 情况4：x，y在前面都有信息。
union_set(x, opp[y]);
union_set(y, opp[x]);
}
}
if(c == 'A'){ // 注意三种情况的判断依据。
if(find_set(x) == find_set(y))
printf("In the same gang.\n");
else if(find_set(x) == find_set(opp[y]))
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
}
}
}
return 0;
}
poj1611：
#include<stdio.h>
int fa[30001];
int rank[30001];
int num[30001];
int make(int x)
{
fa[x]=x;
rank[x]=0;
num[x]=1;
}
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
void unionset(int x,int y)
{
int fx,fy;
x=find(x);
y=find(y);
if(x==y)
return ;
if(rank[x]>rank[y])
{
fa[y]=x;
num[x]+=num[y];
}
else
{
fa[x]=y;
if(rank[x]==rank[y])
rank[y]++;
num[y]+=num[x];
}
return ;
}
int main()
{
int n,m,x,y,i,j,t;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==n&&n==0)
break;
if(m==0)
{
printf("1\n");
continue;
}
for(i=0;i<n;i++)
make(i);
for(i=0;i<m;i++)
{
scanf("%d%d",&t,&x);
for(j=1;j<t;j++)
{
scanf("%d",&y);
unionset(x,y);
x=y;
}
}
x=find(0);
printf("%d\n",num[x]);
}
return 0;
}
#include<stdio.h>
int fa[30001];
int rank[30001];
int num[30001];
int make(int x)
{
fa[x]=x;
rank[x]=0;
num[x]=1;
}
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
void unionset(int x,int y)
{
int fx,fy;
x=find(x);
y=find(y);
if(x==y)
return ;
if(rank[x]>rank[y])
{
fa[y]=x;
num[x]+=num[y];
}
else
{
fa[x]=y;
if(rank[x]==rank[y])
rank[y]++;
num[y]+=num[x];
}
return ;
}
int main()
{
int n,m,x,y,i,j,t;
while(scanf("%d%d",&n,&m)!=EOF)
{
if补充：软件开发 , C++ ,
