Is it a tree? – Omówienie zadania (SPOJ)

Szczegółowe omówienie zadania Is it a tree?

Link do powyższego omówienia zadania Is it a tree?
https://youtu.be/I_Dr_vEnt2A?t=1710

Link do treści zadania Is it a tree?:
https://www.spoj.com/problems/PT07Y/

Dlaczego warto zrobić zadanie Is it a tree?
https://youtu.be/I_Dr_vEnt2A?t=1766

——
Zadanie  Is it a tree? pokazuje
  • co to jest drzewo, jak sprawdzić czy graf jest drzewem
  • jak chodzić po grafie – używa w tym celu algorytmu DFS

——
Jak sprawdzić czy graf jest drzewem?
https://youtu.be/I_Dr_vEnt2A?t=1807

——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625
——–
Zadanie omawia Michał Szeliga – laureat Olimpiady Informatycznej Juniorów:
https://youtu.be/OA8BeVFvaNU?t=830
——-

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> sas[200001]; //Tablica sąsiedztwa
bool vis[200001]; //Tablica odwiedzonych, dzięki której sprawdzimy spójność grafu
void DFS(int v){ //DFS do obliczenia tablicy odwiedzonych
vis[v] = true;
for (int u : sas[v]) if (vis[u] == false) DFS(u);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int i;
int n,m;
cin>>n>>m;
for (i = 0; i < m ; i++){
int a,b;
cin>>a>>b;
sas[a].push_back(b);
sas[b].push_back(a);
//Wczytujemy krawędzie
}
DFS(1); //DFS z dowolnego wierzchołka
bool spojnosc = true;
for (i = 1; i < n+1; i++) if (vis[i] == false) spojnosc = 0; //Jeśli któryś z wierzchołków jest nieodwiedzony, to graf jest niespójny
if (spojnosc == true && m == n-1) cout<<"YES\n";
else cout<<"NO\n";
return 0;
}
Kod C++ programu Is it a tree?, który jest omówiony w powyższym filmie i który otrzymuje 100% 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz