algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Funkcja low - Implementacja w C/C++
Ocena użytkownikóww: *****  / 3
SłabyŚwietny
Nadesłany przez Emil Hotkowski, 02 października 2012 14:18
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

low.cpp:
//Funkcja LOW
//Emil Hotkowski
//www.algorytm.org

#include <iostream>
#include <vector>
#include <algorithm>

#define MX 200005

using namespace std;

vector <int> G[MX];
int PreOrder[MX];
int low[MX];
bool Odwiedzony[MX];

int licznik=1;
void DFS_LOW(int v,int ojciec)
{
     Odwiedzony[v]=1;
     PreOrder[v]=licznik;
     low[v]=licznik++;
     for(int i = 0 ; i < G[v].size();i++)
     {
             if(G[v][i]!=ojciec)
             {
                        if(Odwiedzony[G[v][i]]==1)
                               low[v]=min(low[v],PreOrder[G[v][i]] );
                        else 
                        { 
                               DFS_LOW(G[v][i],v);
                               low[v]=min(low[v],low[G[v][i]]);
                        }
             }
     }
}
Dodaj komentarz