Anonymní profil Tomas678 – Programujte.com

#4 KIIV
To jsem zkousel, ale bez uspechu. Specialita OS X to neni, protoze ani na standardnim Linuxovem stroji to nebezelo.

==4885==
==4885== Process terminating with default action of signal 11 (SIGSEGV)
==4885==  Access not within mapped region at address 0x7FFF5F3FFFF8
==4885==    at 0x100002398: std::stack<int, std::deque<int, std::allocator<int> > >::push(int const&) (in /Users/tomaskrejci/Library/Developer/Xcode/DerivedData/Vrabci-fkeyprufrgyyhkakicphleouivda/Build/Products/Debug/Vrabci)
==4885==  If you believe this happened as a result of a stack
==4885==  overflow in your program's main thread (unlikely but
==4885==  possible), you can try to increase the size of the
==4885==  main thread stack using the --main-stacksize= flag.
==4885==  The main thread stack size used in this run was 8388608.
==4885==
==4885== HEAP SUMMARY:
==4885==     in use at exit: 3,901,923 bytes in 330 blocks
==4885==   total heap usage: 436 allocs, 106 frees, 4,473,199 bytes allocated
==4885==
==4885== LEAK SUMMARY:
==4885==    definitely lost: 0 bytes in 0 blocks
==4885==    indirectly lost: 0 bytes in 0 blocks
==4885==      possibly lost: 0 bytes in 0 blocks
==4885==    still reachable: 3,901,923 bytes in 330 blocks
==4885==         suppressed: 0 bytes in 0 blocks
==4885== Rerun with --leak-check=full to see details of leaked memory
==4885==
==4885== For counts of detected and suppressed errors, rerun with: -v
==4885== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 1 from 1)

Ahoj,

mam problem se zapoctovym programem. Je to Tarjanuv algoritmus na hledani silne souvislych komponent orientovaneho grafu. Po logicke strance by mel byt v poradku. Napriklad kdyz mu zadam na vstup orientovanou kruznici na 30 000 vrcholech, probehne vse v poradku a vystup je spravny. Kdyz ale kruznici zvetsim na 50 000 vrcholu, tak vypise akorat "Segmentation fault: 11". Vsadil bych si na tu rekurzi, ale je mi divne, ze by 50 000 zanoreni nezvladl stack. Navic by mel snad operacni system v pripade potreby stack i dynamicky naskalovat aby vyhovoval. Napada nekoho co s tim?

 Program je v C++, prelozeny na OS X 10.7 prekladacem: 

$ c++ -v
Using built-in specs.
Target: i686-apple-darwin11
Configured with: /private/var/tmp/llvmgcc42/llvmgcc42-2335.15~25/src/configure --disable-checking --enable-werror --prefix=/Developer/usr/llvm-gcc-4.2 --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-prefix=llvm- --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin11 --enable-llvm=/private/var/tmp/llvmgcc42/llvmgcc42-2335.15~25/dst-llvmCore/Developer/usr/local --program-prefix=i686-apple-darwin11- --host=x86_64-apple-darwin11 --target=i686-apple-darwin11 --with-gxx-include-dir=/usr/include/c++/4.2.1
Thread model: posix
gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2335.15.00)

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <limits>

void strongconnect(int v);

struct Vertex
{
    int index, lowlink;
    bool onStack;
    unsigned long hranyZacatek;
    unsigned long hranyKonec;
    
    Vertex()
    {
        index = std::numeric_limits<int>::max();
        lowlink = std::numeric_limits<int>::max();
        onStack = false;
    }
};

std::vector<Vertex> vrcholy;
std::vector<int> hrany;
std::stack<int> zasobnik;
int DFSIndex = 0;

int main (int argc, const char * argv[])
{
    int pocetVrabcu;
    std::cin >> pocetVrabcu;
    
    vrcholy.resize(pocetVrabcu);
    
    int poziceHrany = 0;
    int poziceVrcholu = 0;
        
    for (unsigned long i = 0; i < pocetVrabcu; i++) {
        
        // Zacni nacitat noveho vrabce
        vrcholy[poziceVrcholu].hranyZacatek = poziceHrany;
        
        // Nacti vsechny vrcholy vrabce
        int hrana;
        
        std::cin >> hrana;
        
        while (hrana != 0) {
            hrany.push_back(hrana-1);
            std::cin >> hrana;
            poziceHrany++;
        }
        
        vrcholy[poziceVrcholu].hranyKonec = poziceHrany;
        
        poziceVrcholu++;
    }
        
    for (unsigned i = 0; i < vrcholy.size(); i++) {
        if (vrcholy[i].index == std::numeric_limits<int>::max())
        {
            strongconnect(i);
        }
    }
    
    return 0;
}

void strongconnect(int v)
{
    // Set the depth index for v to the smallest unused index
    vrcholy[v].index = DFSIndex;
    vrcholy[v].lowlink = DFSIndex;
    vrcholy[v].onStack = true;
    zasobnik.push(v);
    ++DFSIndex;
    
    // Consider successors of v
    for (unsigned long i = vrcholy[v].hranyZacatek; i < vrcholy[v].hranyKonec; i++) {
        int w = hrany[i];
        
        if (vrcholy[w].index == std::numeric_limits<int>::max())
        {
            strongconnect(w);
            vrcholy[v].lowlink = std::min(vrcholy[v].lowlink, vrcholy[w].lowlink);
        }
        else if (vrcholy[w].onStack == true)
            vrcholy[v].lowlink = std::min(vrcholy[v].lowlink, vrcholy[w].index);
    }
    
    // If v is a root node, pop the stack and generate an SCC
    if (vrcholy[v].lowlink == vrcholy[v].index)
    {        
        int w;
        
        do {
            w = zasobnik.top();
            vrcholy[w].onStack = false;
            zasobnik.pop();
            std::cout << w+1 << " ";
        } while (w != v);
        
        std::cout << std::endl;
    }
}