Question

C. Kamar Hotel

Time Limit: 2s
Memory Limit: 300 MB

Deskripsi:
Kamu adalah pekerja di suatu hotel. Dan di hotel tersebut ada [tex]N[/tex] kamar, dari nomor [tex]0[/tex] sampai [tex](n-1)[/tex]. Dan semua kamar terkunci kecuali kamar [tex]0[/tex]. Tujuan anda adalah membersihkan semua kamar. Tentu saja kamar tersebut hanya bisa dibuka ketika kamu mempunyai kunci nya.

Saat anda mengunjungi suatu kamar mungkin akan ada beberapa kunci yang bisa kamu gunakan untuk membuka kamar lain yang masih terkunci.

Sekarang pertanyaan - nya. Apakah kamu bisa membersihkan semua kamar atau tidak ?

Masukan:
Baris pertama adalah [tex]N[/tex] banyaknya kamar dan [tex]E[/tex] banyak suatu kunci yang tersimpan pada suatu kamar.
Baris selanjutnya adalah kamar [tex]X_{i}[/tex] dan kunci kamar [tex]Y_{i}[/tex].

+----------------------------------------------+
| [tex]N[/tex] [tex]E[/tex]
| [tex]X_{i}[/tex] [tex]Y_{i}[/tex]
| [tex]X_{.}[/tex] [tex]Y_{.}[/tex]
| [tex]X_{E}[/tex] [tex]Y_{E}[/tex]
+----------------------------------------------+

Keluaran:
Sebuah teks "YA" jika kamu bisa membersihkan semua kamar atau "TIDAK" jika kamu tidak bisa membersihkan semua kamar.

Batasan:
[tex]2 \leq N \leq 10^{3}[/tex]
[tex]2 \leq E \leq 10^{3}[/tex]
[tex]0 \leq X_{i} \leq (n-1)[/tex]
[tex]0 \leq Y_{i} \leq (n-1)[/tex]

1. Contoh:
Masukan:
3 3
0 1
1 2
2 3

Keluaran:
YA

2. Contoh:
Masukan:
3 7
0 1
0 3
1 3
1 0
1 1
2 2
3 0

Keluaran:
TIDAK

Catatan:
Gunakan bahasa pemograman C/C++ untuk menjawab nya.

Answer 1

Jawaban:

#include <iostream>

#include <vector>

using namespace std;

bool canCleanRooms(int n, int e, const vector<int>& x, const vector<int>& y) {

vector<bool> visited(n, false); // Menyimpan status kamar, apakah sudah dikunjungi atau belum

visited[0] = true; // Kamar awal dikunjungi

int count = 1; // Jumlah kamar yang sudah dikunjungi

for (int i = 0; i < e; i++) {

if (visited[y[i]]) { // Jika kunci yang digunakan dapat membuka kamar yang terkunci

if (!visited[x[i]]) { // Jika kamar yang dapat dibuka belum dikunjungi

visited[x[i]] = true; // Tandai kamar tersebut sudah dikunjungi

count++;

}

}

if (count == n) { // Jika semua kamar sudah dikunjungi

return true;

}

}

return false;

}

int main() {

int n, e;

cin >> n >> e;

vector<int> x(e), y(e);

for (int i = 0; i < e; i++) {

cin >> x[i] >> y[i];

}

if (canCleanRooms(n, e, x, y)) {

cout << "YA" << endl;

} else {

cout << "TIDAK" << endl;

}

return 0;

}