UCPC 2020 예선 G / 루머 - 19538

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int N, M;
queue<int> black[2];
vector<vector<int>> adj, blackAdj;
vector<bool> isWhite;
vector<int> ans;
 
void linkBk(int here) {
    for(int i = 0; i<adj[here].size(); ++i) {
        int there = adj[here][i];
        blackAdj[there].push_back(here);
    }
}
 
void update(queue<int>& tmp) {
    while(!tmp.empty()) {
        int u = tmp.front();
        tmp.pop();
        linkBk(u);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    black[0] = black[1] = queue<int>();
    blackAdj = adj = vector<vector<int>>(N+1);
    isWhite = vector<bool>(N+1, true);
    ans = vector<int>(N+1, -1);
    for(int i = 1; i<=N; ++i) {
        int j;
        while(true) {
            cin >> j;
            if(!j) break;
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }
    cin >> M;
    int q;
    for(int i = 0; i<M; ++i) {
        cin >> q;
        black[1].push(q);
        isWhite[q] = false;
        ans[q] = 0;
        linkBk(q);
    }
 
    int iter = 1;
    while(true) {
        queue<int> tmp;
 
        while(!black[iter%2].empty()) {
            int here = black[iter%2].front();
            black[iter%2].pop();
            for(int i = 0; i<adj[here].size(); ++i) {
                int there = adj[here][i];
                if(!isWhite[there]) continue;
                int aBN = blackAdj[there].size();
                int aAN = adj[there].size();
                if(aBN + aBN >= aAN) {
                    isWhite[there] = false;
                    black[(iter+1)%2].push(there);
                    ans[there] = iter;
                    tmp.push(there);
                }
            }
        }
        if(!tmp.size()) break;
        update(tmp);
        ++iter;
    }
    for(int i = 1; i<=N; ++i)
        cout << ans[i] << " ";
}

 

 

 

 

 

https://www.acmicpc.net/problem/19538

19538번: 루머

 

 

 

 

 

루머

이번 타임에 루머를 믿게 되는 사람들은, 모두 바로 직전타임에 루머를 믿게된 사람의 인접한 사람들입니다.

위의 아이디어를 이용해 BFS탐색을 돌려주면 됩니다.