이 글에서는 싱크 노드 수를 그래프로 풀기 위한 중요한 정보를 설명하겠습니다. 이 문제에는 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 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.
위 내용은 C++를 사용하여 그래프에서 싱크 노드 수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!