Qrafik Etibarlı Ağac LeetCode Həlli

Problem bəyanat

Qrafik Etibarlı Ağac LeetCode Həlli – Qrafikin kənarlarını nəzərə alaraq, kənarların etibarlı ağac olub-olmadığını yoxlayın. Əgər belədirsə, əks halda doğru və yalanı qaytarın. Kenarlar n*2 ölçülü 2D massiv kimi verilir

Nümunələr və izahatlar

Misal 1:

Pin

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Explanation: Since it does not conatain any cycle and all

komponentləri birləşdirilir

, it's a valid tree

Misal 2:

Pin

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Explanation: False, because there exists a cycle

Yanaşma

Qrafik etibarlı ağacdır, iff

• ayrılmış komponentlərdən ibarət deyil
• dövrü yoxdur

Alqoritm

Xəritə və kənarlardan istifadə edərək qrafiki quracağıq (2D massiv verilmişdir giriş kimi). DFS/BFS istifadə edərək qrafikdə mövcud olan hər hansı bir dövrü yoxlayın. Ziyarət edilən qovşağı 1 olaraq qeyd edəcəyik və emal zamanı bir az sonra qonşuları üzərindən keçərək eyni qovşaqla qarşılaşırıqsa, bu, qrafikdə bir dövrü ehtiva edir.

Sonra, qrafikdə əlaqəsi kəsilmiş komponentlərin olub olmadığını yoxlayacağıq. Bunun üçün hər hansı node baxılmamış qalıb-qalmadığını yoxlaya bilərik. Əgər varsa, bu, əlaqəsi kəsilmiş komponentlərin olduğunu göstərir.

Kodu

Qrafik Etibarlı Ağac üçün C++ Kodu

class Solution {
    bool isCyclic(map<int, vector<int>> &adj, vector<int>&vis, int v, int u) {
        if(vis[v]) return 1;
        vis[v]=1;
        for(int neighbor:adj[v]) {
            if(neighbor != u && isCyclic(adj, vis, neighbor, v)) 
                return 1;
        }
        return 0;
    }
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        // contruct graph using map
        map<int, vector<int>> adj;
        for(auto &edge: edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        vector<int> vis(n,0);
        
        if(isCyclic(adj, vis, 0, -1))
            return 0;
        
        for(int i=0; i<n; i++) {
            if(!vis[i])
                return 0;
        }
        
        return 1;
    }
};

Qrafik Etibarlı Ağac üçün Java Kodu

class Solution {
    private List<List<Integer>> adj = new ArrayList<>();
    private Set<Integer> vis = new HashSet<>();
    
    boolean dfs(int node, int parent) {
        if (vis.contains(node)) return false;
        vis.add(node);
        for (int neighbour : adj.get(node)) {
            if (parent != neighbour) {
                boolean result = dfs(neighbour, node);
                if (!result) return false;
            }
        }
        return true;
    }
    
    public boolean validTree(int n, int[][] edges) {
        
        if (edges.length != n - 1) return false;
        
        for (int i = 0; i < n; i++)
            adj.add(new ArrayList<>());
        
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        return dfs(0, -1) && vis.size() == n;   
    }

}

Graph Valid Tree LeetCode Həlli üçün Mürəkkəblik Təhlili

E kənarların sayı, N isə qovşaqların sayı olsun.

• Zamanın mürəkkəbliyi: O(N + E)N node və E kənarlarının bitişiklik siyahısını yaratmaq O(E) + O(N) = alacaq. O(N+E) vaxt. Hər bir node əlavə edildiyi kimi məlumatların quruluşu yalnız bir dəfə, N iterasiya olacaq və hər qovşaq üçün onun bitişik kənarları yalnız bir dəfə keçiləcək. Ziyarət edilmiş massiv saxlamaqla bunu təmin edirik. Buna görə də, ümumi E kənarları döngə tərəfindən bir dəfə təkrarlanır və buna görə də zaman mürəkkəbliyi O(N + E) olur.
• Kosmik Mürəkkəblik: O(N + E)Qonşuluq siyahısı E kənarları olan N qovşaqdan ibarətdir, buna görə də O(N + E) boşluğu. Ən pis halda, yığının/növbənin eyni anda bütün N qovşaqları olacaq və nəticədə cəmi O(N) boşluq yaranacaq. Beləliklə, fəzanın mürəkkəbliyi O(E + N) olur.