5 5 10 5 0 5 1 5 2 5 1 5 0 GT 0 GT 3 AP 3 3 GT 3 GT 4 MG 3 4 GT 4 MG 1 3 GT 4 GT 1
Lowest rate: 5. Company 3 is empty. Accept Lowest rate: 3. Company 4 is empty. Accept Company 4 is a part of company 3. Accept Company 4 is a part of company 1. Lowest rate: 3.
#include<stdio.h>
const int N = 100005;
int fath[N],val[N],n;
void init()
{
for(int i=0;i<=n;i++)
fath[i]=i,val[i]=-1;
}
int findfath(int x)
{
if(x!=fath[x])
fath[x]=findfath(fath[x]);
return fath[x];
}
int main()
{
int k,m,a,b;
char st[20];
while(scanf("%d%d%d",&n,&k,&m)>0)
{
init();
while(k--)
{
scanf("%d%d",&a,&b);
if(val[b]==-1||val[b]>a)
val[b]=a;
}
while(m--)
{
scanf("%s",st);
if(st[0]=='A')
{
scanf("%d%d",&a,&b);
if(fath[b]==b)
{
if(val[b]==-1||val[b]>a)
val[b]=a;
printf("Accept\n");
}
else printf("Reject\n");
}
else if(st[0]=='M')
{
scanf("%d%d",&a,&b);
if(fath[a]!=a||fath[b]!=b||a==b)
{
printf("Reject\n"); continue;
}
printf("Accept\n");
if(val[a]==-1||val[b]!=-1&&val[a]>val[b])
val[a]=val[b];
fath[b]=a;
}
else
{
scanf("%d",&a);
if(fath[a]!=a)
{
b=findfath(a);
printf("Company %d is a part of company %d.\n",a,b);
}
else
{
if(val[a]==-1)
printf("Company %d is empty.\n",a);
else printf("Lowest rate: %d.\n",val[a]);
}
}
}
printf("\n");
}
}
原文：http://blog.csdn.net/u010372095/article/details/44263775