290 Gandaci Java

[•Mihai22e]

De ce dintre urmatoarele 2 functii de cuplare

Cod:

inline bool pair_up(int x) {
    if(used[x])
        return 0;
    used[x] = 1;
    for(size_t i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(!R[y]) {
            L[x] = y;
            R[y] = x;
            return 1;
        }
    }
    for(size_t i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(pair_up(R[y])) {
            L[x] = y;
            R[y] = x;
            return 1;
        }
    }
    return 0;
}

si

Cod:

inline bool pair_up(int x) {
    if(used[x])
        return 0;
    used[x] = 1;
    for(size_t i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(!R[y] || pair_up(R[y])) {
            L[x] = y;
            R[y] = x;
            return 1;
        }
    }
    return 0;
}

prima este mai rapida?
Cu alte cuvinte, de ce este mai rapid ca intai sa cuplez nodul x cu un nod catre care am muchie si nu este cuplat, iar abia apoi sa incerc sa-l cuplez cu un nod catre care am muchie si pe care-l decuplez de nodul cu care acesta era cuplat?

[•freak93]

Prima implementare este defapt algoritmul Hopcroft-Karp (complexitatea O(M sqrt(N)), a doua are complexitate mai mare dar in general se comporta cam la fel, tocmai din acest motiv lumea foloseste de multe ori a doua abordare. Nu stiu exact sa-ti zic ce complexitate are a doua abordare.