C++를 사용하여 그래프의 싱크 노드 수 찾기

이 기사에서는 그래프의 싱크 노드 수를 푸는 데 중요한 정보를 설명합니다. 이 문제에는 N개의 노드(1에서 N까지)와 M개의 간선이 있는 방향성 비순환 그래프가 있습니다. 목표는 주어진 그래프에 몇 개의 싱크 노드가 있는지 찾는 것입니다. 싱크 노드는 나가는 가장자리를 생성하지 않는 노드입니다. 여기 간단한 예가 있습니다 -

Input : n = 4, m = 2

Edges[] = {{2, 3}, {4, 3}}
Output : 2

해결책을 찾기 위한 간단한 접근 방식

이 접근 방식에서는 그래프의 가장자리를 살펴보고 가장자리가 나오는 집합의 고유한 요소를 푸시한 다음 존재하는 총 노드 수와 함께 집합의 크기를 뺍니다.

예시

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 4; // number of nodes.
    int m = 2; // number of edges.
    vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
    set<int> s;
    for(int i = 0; i < m; i++){
        s.insert(edges[i].first); // will keep value of
                               // distinct node from which edges are going out.
    }
    cout << n - s.size(); // answer is the total number of nodes - number of non sink nodes.
    return 0;
}

출력

2

위 코드 설명

이 코드에서 우리는 벡터 에지를 통과하고 쌍의 첫 번째 요소를 집합에 삽입합니다. 고유한 요소만 유지하므로 이제 총 노드 수에서 집합의 특정 크기를 뺍니다. 위에 표시된 프로그램은 O(N)의 시간 복잡도를 가집니다. 여기서 N은 그래프에 있는 간선의 수를 나타냅니다.

결론

이 기사에서는 집합을 사용하여 그래프에 존재하는 싱크 노드 수 O(N) 시간 복잡도를 찾는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.