단절점 - 11266

무향그래프에서 dfs 스패닝트리를 만들고 특정 정점을 루트 노드로 하는 subtree에서 선조 노드로 갈수 있는 역방향 간선이 있는지 확인하는 방법을 사용해 풀었습니다.

 

 

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

11266번: 단절점

 

//단절점 - 백준11266
 
#include <iostream>
#include <vector>
using namespace std;
 
int V, E;
vector<vector<int>> adj;
vector<int> discovered;
vector<bool> bucket;
int a_num = 0;
int count = 0;
 
int dfs(int here, bool isRoot)
{
    int ret = discovered[here] = count++;
    int there;
    int c_num = 0;
    for(int i = 0; i<adj[here].size(); i++)
    {
        there = adj[here][i];
        if(discovered[there] == -1)
        {
            ++c_num;
            int subtree = dfs(there, false);
            if(!isRoot && discovered[here] <= subtree)
                bucket[here] = true;
            ret = min(ret, subtree);
        }
        else
            ret = min(ret, discovered[there]);
    }
    if(isRoot && c_num > 1)
        bucket[here] = true;
    if(bucket[here])
        ++a_num;
    return ret;
}
 
void dfsAll()
{
    for (int i = 1; i <= V; i++)
        if (discovered[i] == -1)
            dfs(i, true);
}
 
int main()
{
    cin >> V >> E;
    adj = vector<vector<int>>(V + 1, vector<int>());
    discovered = vector<int>(V + 1, -1);
    bucket = vector<bool>(V + 1, false);
    int x, y;
    for (int i = 0; i < E; i++)
    {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfsAll();
    cout << a_num << endl;
    for (int i = 1; i <= V; i++)
        if (bucket[i])
            cout << i << " ";
}