小煜很快（题解）

小半 • 2023年2月15日上午10:12 • 软件工程 • 阅读 232

题目描述

小煜很快，“358团，谁不知道我是快枪手”，他经常这样说道。
他想和你玩个经典的游戏：将小球用几个杯子盖住然后随机交换位置，再让你猜球在哪个杯子里。当然因为小煜很快，他将不再使用3个杯子，而是使用n个杯子，小球也不止一个。他将进行m次交换。同时因为他很快，他能在一瞬间移动k个杯子。你尽力去跟上他的思必得，不过很可惜，你没能猜中小球的位置。不过没关系，你决定痛定思痛，总结经验，下次赢回来。
你现在知道了所有交换后的小球的位置，并向小煜问来了所有的交换情况。现在你想反推出一开始小球的位置。

输入

第一行有两个数字n和m，意思如题面描述。n和m不大于2000。
之后有m组数据，每组数据第一行是一个数字k，意思如题面描述。k不大于100。之后的k行每行包括两个数字a和b，用空格隔开，表示将a杯子移动到b杯子的位置。
举个例子：
    5
    1 2
    2 3
    3 1
    4 5
    5 4
在这样移动后，杯子由一开始的1 2 3 4 5移动为了3 1 2 5 4。
保证对于任意一个数字x，在这k行数据中要么不出现，要么在左侧右侧各出现一次。
之后有一个数字q，表示有q个小球。
后面跟着q行，每行一个数字p表示字移动后的第p个杯子中有小球。比如上方的例子，p为3，在3 1 2 5 4中对应2，说明一开始在杯子2中有小球。q不大于n，每个p不大于n且不相等。

输出

对每个输入的p输出一个数字，每个数字占一行，表示每个输入的p一开始的位置。

样例输入

样例输出

AC代码

#include<iostream>
#include<queue>
using namespace std;
const int N = 2002;
const int K = 101;

queue <int> q[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        q[i].push(i);
    }
    while(m--){
        int k;
        cin>>k;
        while(k--){
            int c,d;
            cin>>c>>d;
            q[d].push(q[c].front());
            q[c].pop();
        }
    }
    int l;
    cin>>l;
    int f;
    while(l--){
        cin>>f;
        cout<<q[f].front()<<endl;
    }
}