백준 10292번: Man in the Middle (C++)

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

10292번: Man in the Middle

---

Solved By: Articulation

 

주어진 Directed Graph 가운데 Articulation이 존재하는지 찾는 문제였습니다. 존재 여부는 쿼리마다 flag변수를 사용하여 존재한다면 true로 할당하고, Articulation을 구현하여 문제를 풀 수 있었습니다.

#include <iostream>
#include <vector>
#define MAX 30001
using namespace std;

int T;
int n, m;
vector<int> adj[MAX];
int order = 0;
int visitedOrder[MAX];
bool flag = false;

int dfs(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]);
        }
        else{
            child++;
            
            int childMinOrder = dfs(next, false);
            
            if(!isRoot && visitedOrder[now] <= childMinOrder){
                flag = true;
            }
            
            minOrder = min(minOrder, childMinOrder);
        }
    }
    
    if(isRoot && child >= 2){
        flag = true;
    }
    
    return minOrder;
}

int main(){
    cin >> T;
    for(int t = 0; t < T; t++){
        cin >> n >> m;
        
        // init
        order = 0;
        flag = false;
        for(int i = 0; i < MAX; i++){
            adj[i].clear();
            visitedOrder[i] = 0;
        }
        
        for(int i = 0; i < m; i++){
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        dfs(1, true);
        cout << (flag ? "YES" : "NO") << '\n';
    }
}