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 : 2Cara 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 ialahO(N), dengan N mewakili bilangan tepi yang terdapat dalam graf.
KesimpulanDalam 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!
Alat AI Hot
Undress AI Tool
Gambar buka pakaian secara percuma
Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik
AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.
Clothoff.io
Penyingkiran pakaian AI
Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!
Artikel Panas
Alat panas
Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma
SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan
Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa
Dreamweaver CS6
Alat pembangunan web visual
SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)
Struktur Data Bahasa C: Perwakilan Data dan Operasi Pokok dan Grafik
Apr 04, 2025 am 11:18 AM
Struktur Data Bahasa C: Perwakilan data pokok dan graf adalah struktur data hierarki yang terdiri daripada nod. Setiap nod mengandungi elemen data dan penunjuk kepada nod anaknya. Pokok binari adalah jenis pokok khas. Setiap nod mempunyai paling banyak dua nod kanak -kanak. Data mewakili structtreenode {intData; structtreenode*left; structtreenode*right;}; Operasi mewujudkan pokok traversal pokok (predecision, in-order, dan kemudian pesanan) Node Node Carian Pusat Node Node adalah koleksi struktur data, di mana unsur-unsur adalah simpul, dan mereka boleh dihubungkan bersama melalui tepi dengan data yang betul atau tidak jelas yang mewakili jiran.
Bagaimana Debian Readdir Bersepadu Dengan Alat Lain
Apr 13, 2025 am 09:42 AM
Fungsi Readdir dalam sistem Debian adalah panggilan sistem yang digunakan untuk membaca kandungan direktori dan sering digunakan dalam pengaturcaraan C. Artikel ini akan menerangkan cara mengintegrasikan Readdir dengan alat lain untuk meningkatkan fungsinya. Kaedah 1: Menggabungkan Program Bahasa C dan Pipeline Pertama, tulis program C untuk memanggil fungsi Readdir dan output hasilnya:#termasuk#termasuk#includeintMain (intargc, char*argv []) {dir*dir; structdirent*entry; if (argc! = 2) {
Kebenaran di sebalik masalah operasi fail bahasa C
Apr 04, 2025 am 11:24 AM
Kebenaran mengenai masalah operasi fail: Pembukaan fail gagal: Kebenaran yang tidak mencukupi, laluan yang salah, dan fail yang diduduki. Penulisan data gagal: Penampan penuh, fail tidak boleh ditulis, dan ruang cakera tidak mencukupi. Soalan Lazim Lain: Traversal fail perlahan, pengekodan fail teks yang salah, dan kesilapan bacaan fail binari.
Bagaimana untuk memahami keserasian ABI dalam C?
Apr 28, 2025 pm 10:12 PM
Keserasian ABI dalam C merujuk kepada sama ada kod binari yang dihasilkan oleh penyusun atau versi yang berbeza boleh serasi tanpa rekompilasi. 1. Konvensyen Calling Function, 2. Pengubahsuaian Nama, 3. Susun atur Jadual Fungsi Maya, 4. Struktur dan susun atur kelas adalah aspek utama yang terlibat.
Pengaturcaraan Multithreaded Bahasa C: Panduan dan Penyelesaian Masalah Pemula
Apr 04, 2025 am 10:15 AM
C Language Multithreading Programming Guide: Mencipta Threads: Gunakan fungsi pthread_create () untuk menentukan id thread, sifat, dan fungsi benang. Penyegerakan Thread: Mencegah persaingan data melalui mutexes, semaphores, dan pembolehubah bersyarat. Kes praktikal: Gunakan multi-threading untuk mengira nombor Fibonacci, menetapkan tugas kepada pelbagai benang dan menyegerakkan hasilnya. Penyelesaian Masalah: Menyelesaikan masalah seperti kemalangan program, thread stop responses, dan kesesakan prestasi.
Cara mengeluarkan undur dalam bahasa C
Apr 04, 2025 am 08:54 AM
Bagaimana untuk mengeluarkan undur di C? Jawapan: Gunakan pernyataan gelung. Langkah -langkah: 1. Tentukan pembolehubah N dan simpan nombor undur ke output; 2. Gunakan gelung sementara untuk terus mencetak n sehingga n adalah kurang dari 1; 3. Dalam badan gelung, cetak nilai n; 4. Pada akhir gelung, tolak n dengan 1 untuk mengeluarkan timbal balik yang lebih kecil seterusnya.
CS-Week 3
Apr 04, 2025 am 06:06 AM
Algorithms are the set of instructions to solve problems, and their execution speed and memory usage vary. In programming, many algorithms are based on data search and sorting. Artikel ini akan memperkenalkan beberapa algoritma pengambilan data dan penyortiran. Carian linear mengandaikan bahawa terdapat array [20,500,10,5,100,1,50] dan perlu mencari nombor 50. Algoritma carian linear memeriksa setiap elemen dalam array satu demi satu sehingga nilai sasaran dijumpai atau array lengkap dilalui. Carta aliran algoritma adalah seperti berikut: kod pseudo untuk carian linear adalah seperti berikut: periksa setiap elemen: jika nilai sasaran dijumpai: pulih semula benar-benar pelaksanaan bahasa palsu c: #termasuk #termasukintmain (tidak sah) {i
Cara Mendapatkan Format Pengisytiharan Panggilan Definisi Fungsi Bahasa C
Apr 04, 2025 am 06:03 AM
Fungsi bahasa C termasuk definisi, panggilan dan pengisytiharan. Definisi fungsi Menentukan nama fungsi, parameter dan jenis pulangan, fungsi badan melaksanakan fungsi; fungsi panggilan melaksanakan fungsi dan menyediakan parameter; Pengisytiharan fungsi memaklumkan pengkompil jenis fungsi. Nilai pas digunakan untuk pas parameter, perhatikan jenis pulangan, mengekalkan gaya kod yang konsisten, dan mengendalikan kesilapan dalam fungsi. Menguasai pengetahuan ini dapat membantu menulis kod C elegan dan mantap.
