C

题目链接：https://cn.vjudge.net/contest/287775#problem/C

题目大意：给你n个人，然后m条关系，会有k次询问，每一次询问包括两种类型，第一种类型是交换两个人的位置，第二种类型是询问这个人的领导阶层年龄孙是多少、

具体思路：模拟题，我们建立好图之后，通过两个数组来记录当前这个人位置现在是多少。用一个数组是不行的，，举个例子，原来2这个位置变成了4，然后现在4的位置变成了2。如果这个时候要交换2和3,3指向的位置应该是4，而2指向的是3。第一个数组记录现在这个位置是哪个人在，第二个数字记录的是现在这个位置在原图上的位置，因为我们每一次的操作是在原图上进行的，。如果只是一个数组的话，第一次交换没有影响，第二次交换的时候就会有影响了。

father[2]=2.father[3]=3,father[4]=4;

交换3 4

father[2]=2,father[3=4,father[4]=3

交换2 3

father[2]=3,father[3]=2,father[4]=2

这样就有问题了，要连的这个点原来是多少。

AC代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<stdio.h>
 4 #include<algorithm>
 5 #include<map>
 6 #include<cmath>
 7 #include<queue>
 8 #include<cstring>
 9 using namespace std;
10 # define ll long long
11 # define inf 0x3f3f3f3f
12 const int maxn =2e5+100;
13 vector<int>q[maxn];
14 int age[maxn];
15 int father1[maxn];
16 int father2[maxn];
17 int vis[500+100];
18 int minn=inf;
19 void  ask(int t,int val)
20 {
21     minn=min(minn,t==val?inf:age[father2[t]]);
22     for(int i=0; i<q[t].size(); i++)
23     {
24         if(vis[q[t][i]])continue;
25         vis[q[t][i]]=1;
26             ask(q[t][i],val);
27     }
28 }
29 int main()
30 {
31     int n,m,k;
32     scanf("%d %d %d",&n,&m,&k);
33     for(int i=1; i<=n; i++)
34     {
35         scanf("%d",&age[i]);
36         father1[i]=i;
37         father2[i]=i;
38     }
39     int st,ed;
40     for(int i=1; i<=m; i++)
41     {
42         scanf("%d %d",&st,&ed);
43         q[ed].push_back(st);
44     }
45     char str[10];
46     while(k--)
47     {
48      memset(vis,0,sizeof(vis));
49         scanf("%s",str);
50         if(str[0]=='T')
51         {
52             scanf("%d %d",&st,&ed);
53             swap(father1[st],father1[ed]);
54             father2[father1[st]]=st;
55             father2[father1[ed]]=ed;
56        //     cout<<1<<" "<<father1[1]<<" "<<father2[1]<<endl;
57          //   cout<<2<<" "<<father1[2]<<" "<<father2[2]<<endl;
58        //     cout<<3<<" "<<father1[3]<<" "<<father2[3]<<endl;
59         }
60         else if(str[0]=='P')
61         {
62             minn=inf;
63             scanf("%d",&st);
64           ask(father1[st],father1[st]);
65             if(minn==inf)printf("*
");
66             else
67             printf("%d
",minn);
68         }
69     }
70     return 0;
71 }