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

이 글에서는 싱크 노드 수를 그래프로 풀기 위한 중요한 정보를 설명하겠습니다. 이 문제에는 N개의 노드(1~N)와 M개의 간선이 있는 방향성 비순환 그래프가 있습니다. 목표는 주어진 그래프에 싱크 노드가 몇 개 있는지 알아내는 것입니다. 싱크 노드는 나가는 에지를 생성하지 않는 노드입니다. 다음은 간단한 예입니다.

Input : n = 4, m = 2

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

해를 찾는 간단한 방법

이 방법에서는 그래프의 가장자리를 탐색하고 가장자리가 가리키는 집합의 다른 요소를 그래프에 밀어 넣은 다음 집합의 크기를 뺍니다. 존재하는 총 노드 수입니다.

Example

#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;
}

Output

2

위의 코드 설명

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

결론

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

위 내용은 C++를 사용하여 그래프에서 싱크 노드 수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!