文章目录

F. Robots

题意:

0 , 1 , . . n − 1 0,1,..n-1 0,1,..n−1 个路口，每一个路口都有一个红绿灯，按下红灯会走向 a 0 , a 1 , a 2 . . a n − 1 a_0,a_1,a_2..a_{n-1} a0​,a1​,a2​..an−1​,按下绿灯会走向 b 0 , b 1 , b 2 , . . . . b n − 1 b_0,b_1,b_2,....b_{n-1} b0​,b1​,b2​,....bn−1​，开始时，每一个红绿灯都有一个人，问是否存在一种方式，使得，所有的人最后聚在一起?

分析：

最后所有的人都聚在一起，说明任意两个人之间都是可以互相汇合的，也即无论在任何位置，都可以与任意其它位置的人汇合，于是我们从每一个点出发开始广度优先搜索，最后判定是否任意两两之间可达


const int maxn = 600;
bool vis[maxn][maxn];
vector<int> red[maxn],green[maxn];

int main(void)
{
// freopen("input.txt","r",stdin);
// freopen("output1.txt","w",stdout);
    int T;
    cin>>T;
    while(T--){
        int k,n;
        scanf("%d",&k);
        scanf("%d",&n);
        rep(i,0,n) 
         rep(j,0,n)
           vis[i][j] = 0;
        rep(i,0,n) red[i].clear(),green[i].clear();
        for(int i = 0,u;i < n; ++i){
            scanf("%d",&u);
            red[u].push_back(i);
        }
         for(int i = 0,u;i < n; ++i){
            scanf("%d",&u);
            green[u].push_back(i);
        }
        queue<P> Q;
        for(int i = 0;i < n; ++i)
            Q.push(P(i,i)),vis[i][i] = true;
        while(!Q.empty()){
            P p = Q.front();Q.pop();
            for(auto c: red[p.first]){
                for(auto d: red[p.second]){
                   if(!vis[c][d]){
                    vis[c][d] = 1;
                    Q.push(P(c,d));
                   }
                }
            }
            for(auto c: green[p.first]){
                for(auto d: green[p.second]){
                   if(!vis[c][d]){
                    vis[c][d] = 1;
                    Q.push(P(c,d));
                   }
                }
            }
        }
        bool yes = true;
        rep(i,0,n) 
         rep(j,0,n)
           yes &= vis[i][j];
        printf("%d ",k);
        if(yes)
            puts("YES");
        else
            puts("NO");
    }    

   return 0;
}