Qrafikin tam keçə bilən Leetcode həllini saxlamaq üçün maksimum kənar sayını silin

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic ÜberBaxılıb 16

Problem bəyanat

Qrafiki tam keçə bilən Leetcode həlli üçün maksimum kənar sayını silin - Alice və Bob istiqamətləndirilməmiş qrafikə malikdir. n qovşaqlar və 3 növ kənar:

  • Tip 1: Yalnız Alice keçə bilər.
  • Tip 2: Yalnız Bob keçə bilər.
  • Tip 3: Həm Alice, həm də Bob tərəfindən keçə bilər.

Massiv verilmişdir edges hara edges[i] = [typei, ui, vi] növün iki istiqamətli kənarını təmsil edir typei qovşaqlar arasında ui və vi, kənarları çıxardıqdan sonra qrafikin həm Alice, həm də Bob tərəfindən hələ də tam keçə bilməsi üçün çıxara biləcəyiniz kənarların maksimum sayını tapın. Qrafik Alice və Bob tərəfindən tamamilə keçilir, əgər hər hansı bir qovşaqdan başlayaraq bütün digər qovşaqlara çata bilirlər.

Qayıtmaq çıxara və ya geri qaytara biləcəyiniz kənarların maksimum sayı -1 qrafikin Alice və Bob tərəfindən tam keçməsi mümkün deyilsə.

misal

Input:

 n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]

Çıxış:

 2

Qrafikin tam keçə bilən Leetcode həllini saxlamaq üçün maksimum kənar sayını silinPin

Explanation:

Burada qeyd edə bilərik ki, [1,1,2] və [1,1,3] kənarları çıxarıldıqdan sonra qrafik həm Alice, həm də Bob tərəfindən keçə bilir, ona görə də cavab 2-dir.

Yanaşma

Fikir

Buradakı fikir əvvəlcə qrafikin boş olduğunu düşünməkdir və indi biz kənarları əlavə etmək istəyirik graph belə ki, qrafik birləşdirilir. Birlik - Tap ayrı-ayrı komponentlərdəki bütün qovşaqlardan başladığımız və qrafikə kənarlar əlavə edərkən qovşaqları birləşdirdiyimiz belə bir problemi həll etməyin ən asan yoludur.

Bəzi kənarlar yalnız Bob üçün, bəziləri isə yalnız Alice üçün əlçatan olduğundan, onların keçilmə qabiliyyətinə diqqət yetirmək üçün bizim iki fərqli ittifaq tapma obyektimiz olacaq. Xatırlamaq lazım olan əsas şey odur ki, 3-cü tip kənarları 1 və 2-dən üstün tutmalıyıq, çünki onlar eyni anda hər ikisinə kömək edir.

Alqoritm

Burada əsas fikir minimum kənarları birləşdirməkdir ki, bütün qovşaqlar birləşsin. Bunun üçün acgözlüklə düşünürük və əvvəlcə 3-cü tipin kənarlarını emal edirik.

3-cü tip kənarlar üçün, əgər Alice və ya bob üçün yol bağlı deyilsə, yolu birləşdirin və ya Alice və bob üçün yol varsa, biz bu kənarı çıxarırıq.

2-ci tip kənarlar üçün, bob üçün yol bağlıdırsa, bu kənarı çıxarın, əks halda yolu birləşdirin.

Eynilə, 1-ci tip kənarlar üçün, əgər Alice üçün yol bağlıdırsa, bu kənarı çıxarın, əks halda yolu birləşdirin.

Bütün kənarları keçdikdən sonra cavabınızı alacaqsınız.

Kodu

C ++ kodu

class Solution {
public:
    int find(int i,vector<int> &par){
        if(par[i] == -1){
            return i;
        }
        return par[i] = find(par[i],par);
        //path compression.
    }
    bool union_set(int x,int y,vector<int> &par,vector<int> &rnk){
        int s1 = find(x,par);
        int s2 = find(y,par);
        
        if(s1 != s2){
            //union by rank.
            if(rnk[s1] > rnk[s2]){
                par[s2] = s1;
                rnk[s1] += rnk[s2];
            }
            else{
                par[s1] = s2;
                rnk[s2] += rnk[s1];
            }
            return true;
        }
        return false;
    }
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        
        sort(edges.begin(),edges.end(),[](vector<int> &a,vector<int> &b){
            return a[0] > b[0]; 
        });
        // To process the edges of type 3 first we sort the edges vector.
        
        int rem = 0;
        
        vector<int> parAlice(n,-1);
        vector<int> parBob(n,-1);
        vector<int> rnkAlice(n,1);
        vector<int> rnkBob(n,1);
        
        for(int i=0;i<edges.size();i++){
            if(edges[i][0] == 3){
                bool fg1 = union_set(edges[i][1]-1,edges[i][2]-1,parAlice,rnkAlice);
                bool fg2 = union_set(edges[i][1]-1,edges[i][2]-1,parBob,rnkBob);
                if(fg1==false && fg2==false){
                    //alice and bob are both connected to node x and node y so remove this edge.
                    rem += 1;
                }
            }
            else if(edges[i][0] == 2){
                bool fg2 = union_set(edges[i][1]-1,edges[i][2]-1,parBob,rnkBob);
                if(fg2 == false){
                    //bob is connected to node x and node y so remove this edge.
                    rem += 1;
                }
            }
            else{
                bool fg1 = union_set(edges[i][1]-1,edges[i][2]-1,parAlice,rnkAlice);
                if(fg1 == false){
                    //alice is connected to node x and node y so remove this edge.
                    rem += 1;
                }
            }
        }
        
        int co1=0,co2=0;
        for(int i=0;i<n;i++){
            if(parAlice[i]==-1){co1++;}
            if(parBob[i]==-1){co2++;}
            //if the nodes can be connected then there will be only one parent in the parent array.
        }
        if(co1==1 && co2==1){return rem;}
        return -1;
    }
};

Java kodu

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) 
    {
        Arrays.sort(edges, (a, b)->{
            return b[0]-a[0];
        });//giving the priority to third type of edge or the edge which Bob and Alice both can access
        
        //1-based indexing of nodes 
        int []parentAlice= new int[n+1];//Graph 1 for Alice connectedness
        int []parentBob= new int[n+1];//Graph 2 for Bob connectedness
        
        for(int i= 0; i< n+1; i++){//every node is pointing to itself, at first no connection is considered all sets are independent(no dependency) 
            parentAlice[i]= i;
            parentBob[i]= i;
        }
        
        //number of merged unique node for Alice and Bob that are required to maintain the connectedness of Alice and Bob graph nodes//intialised with one because merging happens in pair 
        int mergeAlice= 1;
        int mergeBob= 1;
        
        //number of cyclic or the non dependent node, that are not required for the connectedness of Alice and Bob nodes  
        int removeEdge= 0;
        
        for(int []edge: edges)
        {
            int cat= edge[0];//category of edge 1)edge Alice can only access 2)edge Bob can only access 3)edge both Alice and Bob can access
            int u= edge[1];
            int v= edge[2];
            
            if(cat == 3){//edge both Alice and Bob an access
                
                //creating dependency of nodes in graph 1 and 2 
                boolean tempAlice= union(u, v, parentAlice);
                boolean tempBob= union(u, v, parentBob);
                
                if(tempAlice == true)
                    mergeAlice+= 1;
                
                if(tempBob == true)
                    mergeBob+= 1;
                
                if(tempAlice == false && tempBob == false)//retundant or the cyclic non-dependent edge//both Alice and Bob don't rquire it connection is already there between these pair of nodes
                    removeEdge+= 1;
            }
            else if(cat == 2){//edge Bob can only access 
                
                //creating dependency of nodes in graph 2
                boolean tempBob= union(u, v, parentBob);
                
                if(tempBob == true)
                    mergeBob+= 1;
                else//no merging of set is done, that means that this edge is not required because it will form cycle or the dependency 
                    removeEdge+= 1;
            }
            else{//edge Alice can only access 
                
                //creating dependency of nodes in graph 1
                boolean tempAlice= union(u, v, parentAlice);
                
                if(tempAlice == true)
                    mergeAlice+= 1; 
                else//no merging of set is done, that means that this edge is not required because it will form cycle or the dependency 
                    removeEdge+= 1;
            }
        }
        if(mergeAlice != n || mergeBob != n)//all node are not connected, connectedness is not maintained 
            return -1;
        return removeEdge;//number of edge removed by maintaining the connectedness 
    }
    
    public int find(int x, int[] parent)
    {
        if(parent[x] == x)//when we found the absolute root or the leader of the set 
            return x;
        
        int temp= find(parent[x], parent);
        
        parent[x]= temp;//Path Compression//child pointing to the absolute root or the leader of the set, while backtracking
        
        return temp;//returning the absolute root 
    }
    
    public boolean union(int x, int y, int[] parent)
    {
        int lx= find(x, parent);//leader of set x or the absolute root
        int ly= find(y, parent);//leader of set y or the absolute root
        
        if(lx != ly){//belong to different set merging 
            
            //Rank Compression is not done, but you can do it 
            parent[lx]= ly;
            
            return true;//union done, dependency created
        }
        else
            return false;//no union done cycle is due to this edge 
    }//Please do Upvote, it helps a lot 
}

Qrafiki tam keçə bilən Leetcode həlli saxlamaq üçün maksimum kənar sayını silmək üçün mürəkkəblik təhlili

Zaman mürəkkəbliyi

The bu yanaşmanın zaman mürəkkəbliyi O(E), burada E kənarların sayıdır, çünki biz yolun sıxılmasından və dərəcəyə görə birləşmədən istifadə etdiyimiz üçün tap və ittifaq funksiyası orta hesabla O(1) olur.

Kosmik Mürəkkəblik

The kosmik mürəkkəblik də O(N), burada N qovşaqların sayıdır.

Translate »