C - Boss Gym - 101473C (模拟)

题目链接：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代码：

 #include<iostream>

 #include<stack>

 #include<stdio.h>

 #include<algorithm>

 #include<map>

 #include<cmath>

 #include<queue>

 #include<cstring>

 using namespace std;

 # define ll long long

 # define inf 0x3f3f3f3f

 const int maxn =2e5+;

 vector<int>q[maxn];

 int age[maxn];

 int father1[maxn];

 int father2[maxn];

 int vis[+];

 int minn=inf;

 void  ask(int t,int val)

 {

     minn=min(minn,t==val?inf:age[father2[t]]);

     for(int i=; i<q[t].size(); i++)

     {

         if(vis[q[t][i]])continue;

         vis[q[t][i]]=;

             ask(q[t][i],val);

     }

 }

 int main()

 {

     int n,m,k;

     scanf("%d %d %d",&n,&m,&k);

     for(int i=; i<=n; i++)

     {

         scanf("%d",&age[i]);

         father1[i]=i;

         father2[i]=i;

     }

     int st,ed;

     for(int i=; i<=m; i++)

     {

         scanf("%d %d",&st,&ed);

         q[ed].push_back(st);

     }

     char str[];

     while(k--)

     {

      memset(vis,,sizeof(vis));

         scanf("%s",str);

         if(str[]=='T')

         {

             scanf("%d %d",&st,&ed);

             swap(father1[st],father1[ed]);

             father2[father1[st]]=st;

             father2[father1[ed]]=ed;

        //     cout<<1<<" "<<father1[1]<<" "<<father2[1]<<endl;

          //   cout<<2<<" "<<father1[2]<<" "<<father2[2]<<endl;

        //     cout<<3<<" "<<father1[3]<<" "<<father2[3]<<endl;

         }

         else if(str[]=='P')

         {

             minn=inf;

             scanf("%d",&st);

           ask(father1[st],father1[st]);

             if(minn==inf)printf("*\n");

             else

             printf("%d\n",minn);

         }

     }

     return ;

 }