단절선 - 11400

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

 

 

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

11400번: 단절선

 

 

 

//단절선 찾기 - 백준11400
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int V, E;
vector<vector<int>> adj;
vector<pair<int, int>> ans;
vector<int> discovered;
int counter = 0;
int a_num = 0;
 
bool compare(const pair<int, int>&p1, const pair<int, int>&p2)
{
    if(p1.first == p2.first)
        return p1.second < p2.second;
    return p1.first < p2.first;
}
 
int dfs(int here, int before)
{
    int ret = discovered[here] = counter++;
    int there;
    for (int i = 0; i < adj[here].size(); i++)
    {
        there = adj[here][i];
        if (discovered[there] == -1)
            ret = min(ret, dfs(there, here));
        else if(there != before)
            ret = min(ret, discovered[there]);
    }
    if (before != -1 && ret >= discovered[here])
    {
        ++a_num;
        if (here < before)
            ans.push_back(make_pair(here, before));
        else
            ans.push_back(make_pair(before, here));
    }
    return ret;
}
 
void dfsAll()
{
    for (int i = 1; i <= V; i++)
        if (discovered[i] == -1)
            dfs(i, -1);
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> V >> E;
    adj = vector<vector<int>>(V + 1);
    ans = vector<pair<int, int>>();
    discovered = vector<int>(V + 1, -1);
    int x, y;
    for (int i = 0; i < E; i++)
    {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
 
    dfsAll();
    sort(ans.begin(), ans.end(), compare);
    cout << a_num << endl;
    for(int i = 0; i<ans.size(); i++)
        cout << ans[i].first << " " << ans[i].second << "\n";
}