D. Longest Path in a Directed Acyclic Graph
Time Limit: [tex]2s[/tex]
Memory Limit: [tex]256_{mb}[/tex]
Level: [tex]2000[/tex]
Deskripsi:
Anda diberikan sebuah graf berarah acyclic (DAG) dengan [tex]N[/tex] nodes dan [tex]M[/tex] edges. Tugas Anda adalah mencari panjang jalur terpanjang dalam graf ini. Panjang jalur dihitung sebagai jumlah edge pada jalur terpanjang.
Masukan:
Baris pertama berisi dua bilangan bulat N dan M, menyatakan jumlah nodes dan jumlah edges dalam graf [tex](1 \leq N \leq 10^{3}, 0 \leq M \leq 10^{5})[/tex].
[tex]M[/tex] baris berikutnya berisi dua bilangan bulat [tex]u[/tex] dan [tex]v[/tex], dengan arti bahwa ada edge yang menghubungkan node [tex]u[/tex] ke node [tex]v[/tex] [tex](1 \leq u, v \leq N)[/tex].
Output:
Satu baris berisi sebuah bilangan bulat, yaitu panjang jalur terpanjang dalam graf.
Contoh Input 1:
5 6
1 2
1 3
2 4
2 5
3 4
4 5
Contoh Output 1:
4
Contoh Input 2:
4 3
1 2
1 3
3 4
Contoh Output 2:
3
Contoh Penjelasan:
Pada contoh input pertama, graf memiliki panjang jalur terpanjang adalah 4. Jalur terpanjang yang mungkin adalah 1 → 2 → 4 → 5 .
Pada contoh input kedua, graf memiliki panjang jalur terpanjang adalah 3. Jalur terpanjang yang mungkin adalah 1 → 3 → 4.
Catatan:
Gunakan bahasa pemograman C/C++ untuk menjawab nya.
Time Limit: [tex]2s[/tex]
Memory Limit: [tex]256_{mb}[/tex]
Level: [tex]2000[/tex]
Deskripsi:
Anda diberikan sebuah graf berarah acyclic (DAG) dengan [tex]N[/tex] nodes dan [tex]M[/tex] edges. Tugas Anda adalah mencari panjang jalur terpanjang dalam graf ini. Panjang jalur dihitung sebagai jumlah edge pada jalur terpanjang.
Masukan:
Baris pertama berisi dua bilangan bulat N dan M, menyatakan jumlah nodes dan jumlah edges dalam graf [tex](1 \leq N \leq 10^{3}, 0 \leq M \leq 10^{5})[/tex].
[tex]M[/tex] baris berikutnya berisi dua bilangan bulat [tex]u[/tex] dan [tex]v[/tex], dengan arti bahwa ada edge yang menghubungkan node [tex]u[/tex] ke node [tex]v[/tex] [tex](1 \leq u, v \leq N)[/tex].
Output:
Satu baris berisi sebuah bilangan bulat, yaitu panjang jalur terpanjang dalam graf.
Contoh Input 1:
5 6
1 2
1 3
2 4
2 5
3 4
4 5
Contoh Output 1:
4
Contoh Input 2:
4 3
1 2
1 3
3 4
Contoh Output 2:
3
Contoh Penjelasan:
Pada contoh input pertama, graf memiliki panjang jalur terpanjang adalah 4. Jalur terpanjang yang mungkin adalah 1 → 2 → 4 → 5 .
Pada contoh input kedua, graf memiliki panjang jalur terpanjang adalah 3. Jalur terpanjang yang mungkin adalah 1 → 3 → 4.
Catatan:
Gunakan bahasa pemograman C/C++ untuk menjawab nya.
Untuk menghitung besaran sudut dalam setiap node kita bisa memakai kode berikut.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int jarakTerjauh(vector<vector<int>>& graph, int n) {
vector<int> dalamDerajat(n + 1, 0);
vector<int> dp(n + 1, 0);
// besaran sudut tiap node
for (int i = 1; i <= n; i++) {
for (int j = 0; j < graph[i].size(); j++) {
int node = graph[i][j];
dalamDerajat[node]++;
}
}
Pembahasan
Di dalam sebuah algoritma untuk sortir seperti di atas besaran sudut dalam dihitung dengan cara melakukan loop (iteration) di sepanjang tepian grafik yang diberikan. Dalam hal ini digunakan variabel dalamSudut untuk menentukan node mana yang posisinya ada di degree 0, dengan demikian bisa dilakukan penyortiran.
Pelajari lebih lanjut
#BelajarBersamaBrainly #SPJ1