10. [C++] 가중치가 없는 그래프에서 사이클 탐지 및 지름 구하기

문제)

N개의 정점과 M개의 간선을 가진 가중지가 없는 그래프 G가 주어진다. 

그래프 G 에서 사이클을 이루는 노드들이 존재할 경우 사이클에 포함된 노드를 제거한 이후 남은 노드 및 간선에서 가장 먼 두 노드의 거리를 출력한다.

 

예시 입력)

10 11
1 2
2 3
3 1
3 4
4 5
5 6
2 7
8 9
9 10

 

단계1. 가중치가 없는 양방향 그래프를 구성한다. 
 : 연결 확인 시 어느 방향으로든 이동 가능한 경우 graph[A].push_back(B), graph[B].push_back(A)로 인접리스트 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 100005;
vector<int> graph[MAX];

int main() {
    int N, M;
    cin >> N >> M;

    // 양방향 그래프 입력
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

 

단계2. 사이클을 찾고 사이클에 포함된 노드들을 표시 

방법 - 위상 정렬 방식 사용

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 100005; //노드의 수
vector<int> graph[MAX]; 
int degree[MAX]

int main() {
    int N, M;
    cin >> N >> M;

    // 양방향 그래프 입력
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }
    queue<int> q;
    
    //차수가 1이하인 노드를 큐에 넣기
    for(int i == 1; i<=N; ++i) {
    	if (degree[i] == 1) q.push(i)
    }
    
    while(!q.empty()){
    	int node = q.front();
        q.pop();
        degree[node] = 0; //제거된 노드 표시
        
        for(int next : graph[node]){
        	if(degree[next] == 0) continue;//제거된 노드
            degree[next]--;
            if(degree[next] == 1){
            	q.push(next);
            }
        }
	}
    //degree[i] >0 이면 사이클에 포함된 노드
    
}

 

단계 3 사이클에 포함된 노드를 제거 후 (degree[i] = 0 이면 제거된 노드로 간주) 남은 노드와 간선에서 연결된 그래프 중 가장 먼 거리를 출력

방법1. BFS를 두번 수행하여 최대 지름 구하기

1. 아무 노드 A에서 가장 먼 노드 B를 BFS로 찾는다.

2. 노드 B에서 다시 BFS하여 가장 먼 거리를 찾는다. 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 100005;
vector<int> graph[MAX];
int degree[MAX];
int N, M;

int farthest_node;
int max_distance;

void bfs(int start) {
    vector<int> dist(N + 1, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    farthest_node = start;
    max_distance = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : graph[u]) {
            if (degree[v] != 0 || dist[v] != -1) continue; // 제거되지 않은 노드는 무시
            dist[v] = dist[u] + 1;
            q.push(v);

            if (dist[v] > max_distance) {
                max_distance = dist[v];
                farthest_node = v;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (degree[i] == 1) q.push(i);
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        degree[node] = 0; // 제거

        for (int next : graph[node]) {
            if (degree[next] == 0) continue;
            degree[next]--;
            if (degree[next] == 1) {
                q.push(next);
            }
        }
    }

    vector<bool> visited(N + 1, false);
    int max_diameter = 0;

    for (int i = 1; i <= N; ++i) {
        if (degree[i] == 0 && !visited[i]) {
            // 첫 BFS - 임의 노드에서 가장 먼 노드 찾기
            bfs(i);
            int first_node = farthest_node;

            // 두 번째 BFS - 첫 BFS에서 찾은 노드에서 가장 먼 거리 찾기
            bfs(first_node);
            int diameter = max_distance;

            max_diameter = max(max_diameter, diameter);

            // 방문 처리 (사이클 제거된 노드만)
            queue<int> comp_q;
            comp_q.push(i);
            visited[i] = true;

            while (!comp_q.empty()) {
                int u = comp_q.front();
                comp_q.pop();
                for (int v : graph[u]) {
                    if (degree[v] == 0 && !visited[v]) {
                        visited[v] = true;
                        comp_q.push(v);
                    }
                }
            }
        }
    }

    cout << "최대 지름: " << max_diameter << '\n';

    return 0;
}

방법2 DFS를 두번 하여 그래프의 지름 구하기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 100005;
vector<int> graph[MAX];
int degree[MAX];
int N, M;

vector<bool> visited;
int max_depth = 0;
int farthest_node = 0;

void dfs(int node, int depth) {
    visited[node] = true;

    if (depth > max_depth) {
        max_depth = depth;
        farthest_node = node;
    }

    for (int next : graph[node]) {
        if (degree[next] == 0 && !visited[next]) { // 사이클 제거된 노드만
            dfs(next, depth + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (degree[i] == 1) q.push(i);
    }

    while (!q.empty()) {
        int node = q.front(); q.pop();
        degree[node] = 0;

        for (int next : graph[node]) {
            if (degree[next] == 0) continue;
            degree[next]--;
            if (degree[next] == 1) q.push(next);
        }
    }

    int max_diameter = 0;
    visited.assign(N + 1, false);

    for (int i = 1; i <= N; ++i) {
        if (degree[i] == 0 && !visited[i]) {
            max_depth = 0;
            farthest_node = i;

            dfs(i, 0); // 임의 노드에서 가장 먼 노드 찾기

            visited.assign(N + 1, false); // 방문 초기화
            max_depth = 0;
            dfs(farthest_node, 0); // 거기서 가장 먼 거리 찾기

            max_diameter = max(max_diameter, max_depth);
        }
    }

    cout << "최대 지름: " << max_diameter << '\n';
    return 0;
}

 

위 문제와 연관된 예제 문제는 아래와 같다

 

30870번: 사이클 없는 그래프 만들기

1167번: 트리의 지름