Baymax

열심히 화이팅

1 분 소요

문제Permalink

그래프가 주어졌을 때, 단절점을 모두 구하는 프로그램을 작성하시오. 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 이상으로 나누어지는 정점을 말한다.

입력Permalink

첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다.
다음 E개의 줄에는 간선 정보를 나타내는 두 정수 A, B가 주어진다.
이는 A번 정점과 B번 정점이 연결되어 있다는 뜻이다.

예제 입력 1Permalink

7 7
1 4
4 5
5 1
1 6
6 7
2 7
3 7

출력Permalink

첫째 줄에 단절점의 개수를 출력한다. 둘째 줄에는 단절점의 번호를 공백으로 구분해 오름차순으로 출력한다.

예제 출력 1Permalink

3
1 6 7

풀이Permalink

문제 해결 방법Permalink

이 문제는 DFS를 사용하여 그래프의 단절점을 찾는 문제입니다. 단절점을 찾기 위한 주요 단계는 다음과 같습니다:

  1. DFS 순회: 그래프를 DFS로 순회하면서 각 정점의 방문 순서를 기록합니다.
  2. Low Link Value: 각 정점에서 도달할 수 있는 가장 일찍 방문한 정점의 번호를 계산합니다.
  3. 단절점 판별:
    • 루트 노드: 자식이 2개 이상이면 단절점
    • 그 외 노드: 자식 노드들 중 하나라도 자신보다 낮은 정점으로 가지 못하면 단절점

이 알고리즘의 시간 복잡도는 O(V + E)입니다.

코드Permalink

#include<vector>
#include<stdio.h>
#include<algorithm>

using namespace std;

int n,m;
vector<int> mp[10001];
int dist[10001],dd;
int cut[10001];

int dfs(int node,bool r)
{
    dist[node]=++dd;
    int rtn = dd;
    int child=0;
    for(int p : mp[node])
    {
        if(dist[p]==0)
        {
            child++;
            int child_low = dfs(p,0);
            if(!r&&child_low>=dist[node])
            {
                cut[node]=1;
            }
            rtn = min(rtn,child_low);
        }
        else
            rtn = min(rtn,dist[p]);
    }
    if(r&&child>1)
    {
        cut[node]=1;
    }
    return rtn;
}

int main()
{
    int i,j,x,y;
    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        mp[x].push_back(y);
        mp[y].push_back(x);
    }

    for(i=1;i<=n;i++)
        if(dist[i]==0)
            dfs(i,true);
    int ans = 0;
    for(i=1;i<=n;i++)
    {
        ans+=cut[i];
    }
    printf("%d\n",ans);
    for(i=1;i<=n;i++){
        if(cut[i])printf("%d ",i);
    }
    return 0;
}

댓글남기기

참고