절단점 찾기

int V,E,cnt=1;
vector<int>adj[MAX_N],discoverd;
vector<bool>isCutVertex;

int findCutVertex(int u,bool isRoot)
{
    discoverd[u]=cnt++;
    int ret=discoverd[u],child=0;
    for(auto v:adj[u])
    {
        if(!discoverd[v])
        {
            child++;
            int subtree=findCutVertex(v,false);
            if(!isRoot&&subtree>=discoverd[u])isCutVertex[u]=true;
            ret=min(ret,subtree);
        }
        else ret=min(ret,discoverd[v]);
    }
    if(isRoot&&child>=2)isCutVertex[u]= true;
    return ret;
}

• 선행 알고리즘: DFS,그래프 기초
• 무향 그래프의 절단점(cut vertex)이란? 한 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두개 이상으로 나뉘어지는 정점.
• 무향 그래프의 특징인 교차 간선이 없다는 점을 활용한다. u가 지워졌을 때 그래프가 쪼개지지 않는 유일한 경우는 u의 선조와 자손들이 전부 역방향 간선으로 연결되어 있을 때이다.
• u가 루트일 경우에는 조금 다르게 판정을 해야한다. 자손이 하나도 없거나 하나만 있을 경우 u가 없어져도 그래프가 쪼개지지 않는다.
• findCutVertex()함수는 연결되어 있는 간선중 가장 일찍 발견된 정점을 반환하게 한다. 즉, 가장 루트와 가까운 점을 반환하여 판단한다.
• 기본 예제

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

11266번: 단절점