Cari bilangan nod sinki dalam graf menggunakan C++

Dalam artikel ini, kami akan menerangkan maklumat penting untuk menyelesaikan bilangan nod sinki dalam graf. Dalam masalah ini, kita mempunyai graf asiklik terarah dengan nod N (1 hingga N) dan tepi M. Matlamatnya adalah untuk mengetahui berapa banyak nod sinki yang terdapat dalam graf tertentu. Nod sink ialah nod yang tidak menghasilkan sebarang tepi keluar. Berikut ialah contoh mudah -

Input : n = 4, m = 2

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

Cara mudah untuk mencari penyelesaian

Dalam pendekatan ini, kita akan melintasi tepi graf dan menambah set yang ditunjuk oleh tepi. elemen yang berbeza ditolak ke dalamnya dan kemudian saiz set ditolak daripada jumlah bilangan nod yang ada.

Contoh

#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

Penerangan kod di atas

#🎜 menilai kod ini🎜# tepi vektor dan memasukkan elemen pertama pasangan ke dalam set. Ia hanya menyimpan elemen yang berbeza, jadi sekarang kita akan menolak saiz khusus koleksi daripada jumlah bilangan nod. Kerumitan masa program yang ditunjukkan di atas ialah

O(N), dengan N mewakili bilangan tepi yang terdapat dalam graf.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari bilangan nod sinki yang terdapat dalam graf dalam kerumitan masa O(N) menggunakan bantuan set. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan kaedah lengkap untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Cari bilangan nod sinki dalam graf menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!