When ALPC42 got to a panzer brigade, He was asked to build software to help them regroup the battalions or companies. 
As the tradition of army, soldiers are rated according his or her abilities, taking the rate as an integer. The fighting capacity of a company is determined by the soldier in this company whose rate is lowest. Now the recruits those rated are coming and join to their companies according to the order form HQ. 
With the coming of new recruits, a big regroup action reached, asking to merge some companies into one. The designation of a company, however, will not be canceled, but remain for memorialize what the company is done, means the designation of the company is still exist, but the company is gone, so it is unable to ask recruits to join this company, or merge the company into others. 
A strange thing is, the orders sometimes get wrong, send newbie to a company which is already merged into another, or mentioned some only-designation-existed companies. Such order could be rejected. 
The brigadier wants to know every change of each order, so the program should able to report the status of every order, telling whether it is accept, and can query the fighting capacity of specified company. (To simplify, companies are numbered from 0 to n-1 

Input

There may be several test cases. 
For each case, the integers in first line, n, k, m, telling that there are n companies, k soldiers already, and m orders needs be executed. (1<=n ,k ,m<=100000).
Then k lines with two integers R and C for each, telling a soldier with rate R is now in company C 
Then m lines followed, containing 3 kinds of orders, in upper case: 
  AP x y 
A recruit with ability rate x were asked to join company y. (0<=x<2^31, 0<=y<n) 

  MG x y 
Company x and company y is merged. The new company is numbered as x. (0<=x, y<n) 

  GT x 
Report the fighting capacity of company x. (0<=x<n)

Output

For each order there is exact one line to report the result. 
For AP and MG order, print “Accept” if it is able to be done, and execute it, or “Reject” if it is an illegal order. 
For GT order, if company x is still exist (not merged into others), print as “Lowest rate: y.” which y is the minimal rate of soldiers in this company. If there is no one in this company, tell "Company x is empty." If company x is already merged into others, print "Company x is a part of company z." z is the company where the company x is in. 
Print a blank line after each case 

Sample Input

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

Sample Output

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.

借用一下大神的题意：

有n个军旅 ，现在有m个兵，有k个操作，
对于接下来的m行，表示战斗力为x的兵现在在军旅y中，对于三种操作：
1、AP：让一个战斗力为x的兵加入军旅y中。
2、GT：查询军旅x。如果军旅x中没兵输出空，如果军队有兵并且自己没有被其他军队管辖，那么输出军队中战斗力最渣的战斗力值。如果军队被其他军队所管辖，那么输出其管辖他的军旅编号。
3、MG:让军旅y置于军旅x之下管辖。
这里有一个条件，如果当前军队没有被其他军队管辖的情况下，是可以有新兵加入的，也可以有其他军队加入这个军队的，不过如果当前军队已经被其他军队管辖了，那么新兵是进不来的；军旅也一样，如果当前军旅已经被其他军旅管辖了，那么这个军旅也不能再让其他军旅管辖了。
--------------------- 
作者：键盘上的精灵 
来源：CSDN 
原文：https://blog.csdn.net/yangkunpengD/article/details/51508543 

题解：做过分类并查集那题就知道这题怎么做了。设置一个新数组维护每个军旅的最小值

然后合并的时候要记得维护，有一个小坑我在代码里写上了

#include <bits/stdc++.h>
#define maxn 1000000+5
#define INF 0x3f3f3f3f
using namespace std;
int  pre[maxn];
int Find(int x)
{
    int r=x;
    while(r!=pre[r])
        r=pre[r];
    int i=x,j;
    while(pre[i]!=r) {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}
int a[maxn];int n,m,k;
void mix(int x,int y) {
    int fx=Find(x),fy=Find(y);
    if(fx!=fy)  {
        pre[fy]=fx;
        a[fx]=min(a[fx],a[fy]);
    }
}
void init(){
    for(int i=0;i<=n;i++)pre[i]=i;
    for(int i=0;i<=n;i++)a[i]=INF;
}
int main(){
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        init();
        for(int i=0;i<m;i++){
            int nowx,nowy;
            scanf("%d%d",&nowx,&nowy);
            a[nowy]=min(a[nowy],nowx);
        }
        for(int i=0;i<k;i++){
            char str[10];
            scanf("%s",str);
            if(str[0]=='A'){
                int nowx,nowy;
                scanf("%d%d",&nowx,&nowy);
                if(Find(nowy)==nowy){
                    a[nowy]=min(nowx,a[nowy]);
                    printf("Accept\n");
                }else  printf("Reject\n");
            }else if(str[0]=='G'){
                    int nowy;
                    scanf("%d",&nowy);
                    if(Find(nowy)==nowy){
                        if(a[nowy]==INF)printf("Company %d is empty.\n",nowy);
                        else  printf("Lowest rate: %d.\n",a[nowy]);
                    }else  printf("Company %d is a part of company %d.\n",nowy,Find(nowy));
            }else if(str[0]=='M'){
                int nowx,nowy;
                scanf("%d%d",&nowx,&nowy);
                if(Find(nowx)==nowx&&Find(nowy)==nowy&&nowx!=nowy){//这边是个小坑，看条件
                    mix(nowx,nowy);
                    printf("Accept\n");
                }else printf("Reject\n");
            }
        }
        printf("\n");
    }
}