BOJ 8452 - 그래프와 쿼리 (P1)

사용 알고리즘

BFS + Offline Query

 

풀이

일단 간선 삭제 -> 뒤집으면 간선 추가는 유명하다.

그러고 나서 안될 것 같은 naive한 풀이를 짜면 된다. 그냥 간선이 추가되서 완화되는 정점들을 일일히 탐색하면 된다.

이게 되는 이유를 생각해보자. 1에서 각 정점까지 가는 최단경로는 O(N)일 것이다. (정점이 N개이므로) 그러므로 최단경로가 완화되는 경우도 O(N)일 것이다. 그리고 그러한 정점이 N개 있으므로 전체에서 완화되는 횟수가 O(N^2)이다. 그리고 O(M)개의 간선은 완화될때마다 한번씩 보게 되고, 완화되는 횟수는 말했듯이 정점당 O(N)이므로 간선을 O(NM)번 보게 된다. 따라서 그냥 구현해주면 되며, O(N(N+M)+Q)에 풀린다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll dist[1010];
ll n, m, q;
vector<ll> adj[1010];
vector<P> edge;
inline void relax(ll x){
    queue<ll> q;
    q.push(x);
    while(q.size()){
        ll cur = q.front(); q.pop();
        for(ll next : adj[cur]){
            if(dist[next] > dist[cur]+1){
                dist[next] = dist[cur]+1;
                q.push(next);
            }
        }
    }
}
bool chk[101010];
vector<P> query;
ll ans[202020];
int main(){
    fast;
    fill(dist,dist+1010,1e18);
    dist[1]=0;
    cin>>n>>m>>q;
    edge.resize(m); query.resize(q);
    for(auto &[a,b] : edge)cin>>a>>b;
    for(auto &[a,b] : query){
        char c; cin>>c>>b;
        if(c=='U')a = 1, b--, chk[b]=1;
        else a = 2;
    }
    for(int i = 0 ; i < m ; i++){
        if(!chk[i]){
            adj[edge[i].X].push_back(edge[i].Y);
            if(dist[edge[i].X]+1 < dist[edge[i].Y]){
                dist[edge[i].Y] = dist[edge[i].X]+1;
                relax(edge[i].Y);
            }
        }
    }
    for(int i = q-1 ; i >= 0 ; i--){
        auto [a,b] = query[i];
        if(a==1){
            adj[edge[b].X].push_back(edge[b].Y);
            if(dist[edge[b].X]+1 < dist[edge[b].Y]){
                dist[edge[b].Y] = dist[edge[b].X]+1;
                relax(edge[b].Y);
            }
        }
        else ans[i] = dist[b];
    }
    for(int i = 0 ; i < q ; i++){
        if(ans[i]>0){
            if(ans[i]==1e18)ans[i]=-1;
            cout<<ans[i]<<"\n";
        }
    }
}