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

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