백준 14675번: 단절점과 단절선 (C++)

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

14675번: 단절점과 단절선

---

Solved By: Articulation

 

방금 공부한 Articulation Point와 Edge를 사용해보았습니다.

#include <iostream>
#include <vector>
#include <set>
#include <memory.h>
#define MAX 100001
using namespace std;

int n, q;
vector<int> adj[MAX];
bool isCut[MAX];
int visitedOrder[MAX];
int order = 0;
set<pair<int, int>> cutEdge;
vector<pair<int, int>> edges;

int dfsPoint(int now, bool isRoot){
    int minOrder = visitedOrder[now] = ++order;
    int child = 0;
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next]){
            minOrder = min(minOrder, visitedOrder[next]);
            continue;
        }
        
        child++;
        int childOrder = dfsPoint(next, false);
        
        if(!isRoot && visitedOrder[now] <= childOrder){
            isCut[now] = true;
        }
        
        minOrder = min(minOrder, childOrder);
    }
    
    if(isRoot){
        isCut[now] = (child >= 2);
    }
    
    return minOrder;
}

int dfsEdge(int now, int par){
    int minOrder = visitedOrder[now] = ++order;
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(next == par) continue;
        
        if(visitedOrder[next]){
            minOrder = min(minOrder, visitedOrder[next]);
            continue;
        }
        
        int childOrder = dfsEdge(next, now);
        
        if(childOrder > visitedOrder[now]){
            cutEdge.insert({now, next});
            cutEdge.insert({next, now});
        }
        
        minOrder = min(minOrder, childOrder);
    }
    
    return minOrder;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges.push_back({a, b});
    }
    
    dfsPoint(1, true);
    order = 0;
    memset(visitedOrder, 0, sizeof(visitedOrder));
    dfsEdge(1, 0);
    
    cin >> q;
    for(int i = 0; i < q; i++){
        int Q; cin >> Q;
        if(Q == 1){
            int k; cin >> k;
            if(isCut[k]) cout << "yes";
            else cout << "no";
        }
        else{
            int k; cin >> k;
            if(cutEdge.count(edges[k - 1]) == 1){
                cout << "yes";
            }
            else cout << "no";
        }
        
        cout << '\n';
    }
    
    return 0;
}