#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

FILE *plik;
FILE *plik2;
__int64 freq,start,end,diff;

typedef struct elem{
    int dane;
    elem *nast;
};

typedef struct edge{
    int start;
    int end;
};

int **macierz,*odwiedzone,*out,*tablica;
int licznik, licznikKrawedzi,N;
elem **nastepnicy;
edge **krawedzie;

void sortMacierz();
void createMacierz();
void sortListaN();
void createListaN();
void sortKrawedzie();
void createKrawedzie();
void cleanUp();
void createArrays(int n);

using namespace std;


int main()
{
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
    cout << "podaj N: "; cin >> N; cout << endl;
    createArrays(N);

    cleanUp();

    createMacierz();
    QueryPerformanceCounter((LARGE_INTEGER*)&start);
    sortMacierz();
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    diff = ((end-start)*10000)/freq;
    unsigned int ms = (unsigned int)(diff);
    cout << ms << endl;

    cleanUp();

    createListaN();
    QueryPerformanceCounter((LARGE_INTEGER*)&start);
    sortListaN();
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    diff = ((end-start)*10000)/freq;
    ms = (unsigned int)(diff);
    cout << ms << endl;

    cleanUp();

    createKrawedzie();
    QueryPerformanceCounter((LARGE_INTEGER*)&start);
    sortKrawedzie();
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    diff = ((end-start)*10000)/freq;
    ms = (unsigned int)(diff);
    cout << ms << endl;

    cin >> N;
    return 0;
}

void visitMacierz(int n);
void visitNastepnicy(int n);
void visitKrawedzie(int n);
void losujTablice();
void quick(int *tabl, int *tabl2, int l, int p);

void createArrays(int n) {
    macierz = new int*[n];
    for(int i=0;i<N;i++) macierz[i]=new int[n];
    nastepnicy = new elem*[n];
    krawedzie = new edge*[n*n/4];
    odwiedzone = new int[n];
    out = new int[n];
    tablica = new int[n];

}

void cleanUp() {
    for(int i=0;i<N;i++) {
        odwiedzone[i]=0;
        out[i]=0;
    }
    licznik = 0;
    licznikKrawedzi = 0;
    losujTablice();
}

void losujTablice() {
    plik2 = fopen("c:\liczby.txt","rt");
    for(int i=0;i<N;i++) {
        //fscanf(plik2,"%d/n",&tablica[i]);
        tablica[i]=i+1;
    }
    fclose(plik2);
}

void createKrawedzie(){
        cout << "Lista krawedzi";
    int k;
    plik = fopen("c:\graf.txt","rt");
    //wczytywanie grafu i tworzenie listy krawedzi
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) {
            fscanf(plik,"%d ",&k);
            if (k==1) {
                edge *t = new edge;
                t->start = i;
                t->end = j;
                krawedzie[licznikKrawedzi] = t;
                licznikKrawedzi++;
            }
        }
        odwiedzone[i]=0;
        fscanf(plik,"
");
    }
    fclose(plik);
    cout << ".";
}

void sortKrawedzie() {
    //odwiedzanie wierzcholkow
        int j = 0; int i = 0;
        while(krawedzie[j]) {
            if(krawedzie[j]->start == i) {
                 if(odwiedzone[krawedzie[j]->start]==1){
                     i++;
                    if(odwiedzone[krawedzie[j]->end]!=1) visitKrawedzie(krawedzie[j]->end);
                } else {
                    visitKrawedzie(krawedzie[j]->start);
                }
            }
            j++;
        }
        for(int i=0;i<N;i++) {
            if(odwiedzone[i]!=1) visitKrawedzie(i);
        }
    cout << ".";
     //sortowanie tablic. mozna obejsc koniecznosc sortowanie wpisujac wiercholki odrazu do po ich odwiedzeniu do tablicy ale mi to nie dzialalo.
    quick(out,tablica,0,N-1);
    cout << ".";
    //wypisanie tablicy (mozna ja odwrocic albo tak jak tu zczytywac od konca)
    /*
    cout << "kolejnosc wierzcholkow: " << endl;
    for(int s=N;s>0;s--) {
        cout << tablica[s-1] << " ";
    }
    */
    cout << endl;
}

void createMacierz() {
    cout << "Macierz sasiedztwa";
    plik = fopen("c:\graf.txt","rt");
    //wczytywanie pliku do macierzy
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            fscanf(plik,"%d ",&macierz[i][j]);
        }
        odwiedzone[i]=0;
        fscanf(plik,"
");
    }
    cout << ".";
    fclose(plik);
}

void sortMacierz() {
    //odwiedzanie wierzcholkow
    for(int i=0;i<N;i++) {
        if(odwiedzone[i]!=1) {
            visitMacierz(i);
        }
    }
    cout << ".";
    //sortowanie tablic. mozna obejsc koniecznosc sortowanie wpisujac wiercholki odrazu do po ich odwiedzeniu do tablicy ale mi to nie dzialalo.
    quick(out,tablica,0,N-1);
    cout << ".";
    //wypisanie tablicy (mozna ja odwrocic albo tak jak tu zczytywac od konca)
    /*cout << "kolejnosc wierzcholkow: " << endl;
    for(int s=N;s>0;s--) {
        cout << tablica[s-1] << " ";
    }
    */
    cout << endl;
}

void createListaN() {
    cout << "Lista nastepnikow";
    plik = fopen("c:\graf.txt","rt");
    //tworzenie listy nastepnikow
    int k;
    elem *t,*g,*p = NULL;
    for(int i=0;i<N;i++) {
        t=NULL;
        for(int j=0;j<N;j++) {
            fscanf(plik,"%d ",&k);
            if (k==1) {
                licznikKrawedzi++;
               if(t==NULL) {
                   t = new elem;
                   t->dane = j;
                   t->nast = NULL;
                   p = t;
               } else {
                   g = new elem;
                   g->dane = j;
                   p->nast = g;
                   g->nast = NULL;
                   p = g;
               }
            }
        }
        nastepnicy[i] = t;

    }
    cout << ".";
    fclose(plik);
}

void sortListaN() {
    //odwiedzanie wierzcholkow
    for(int i=0;i<N;i++) {
        if(odwiedzone[i]!=1) visitNastepnicy(i);
    }
    cout << ".";
    //sortowanie tablic. mozna obejsc koniecznosc sortowanie wpisujac wiercholki odrazu do po ich odwiedzeniu do tablicy ale mi to nie dzialalo.
    quick(out,tablica,0,N-1);
    cout << ".";
    //wypisanie tablicy (mozna ja odwrocic albo tak jak tu zczytywac od konca)
/*
    cout << "kolejnosc wierzcholkow: " << endl;
    for(int s=N;s>0;s--) {
        cout << tablica[s-1] << " ";
    }
*/
   cout << endl;
}

void visitKrawedzie(int n) {
    odwiedzone[n] = 1;
    for(int i=0;i<licznikKrawedzi;i++) {
        if(krawedzie[i]->start==n) {
            if(odwiedzone[krawedzie[i]->end]!=1) visitKrawedzie(krawedzie[i]->end);
        }
    }
    out[n] = licznik;
    licznik++;
}

void visitNastepnicy(int n) {
    //cout << "visit: " << n << endl;
    odwiedzone[n]=1;
    elem *t = nastepnicy[n];
    if (t!=NULL) {
        //cout << "znalazl: " << t->dane << endl;
            while(t!=NULL) {
            if(odwiedzone[t->dane]!=1) visitNastepnicy(t->dane);
            t = t->nast;
            //i++;
        }
    } else {
        //cout << "wierzcholek: " << n << "  nie ma nastepnikow" << endl;
    }
    out[n] = licznik;
    licznik++;
}

void visitMacierz(int n) {
    odwiedzone[n]=1;
    for(int i=0;i<N;i++) {
        if (macierz[n][i]==1&&odwiedzone[i]!=1) visitMacierz(i);
    }
    out[n] = licznik;
    licznik++;
}

void quick(int *tabl, int *tabl2, int l, int p) {
    int v=tabl[(l+p)/2];
    int i,j; i=l; j=p;
    do {
        while (tabl[i]<v) i++;
        while (v<tabl[j]) j--;
        if (i<=j) {
            swap(tabl[i],tabl[j]);
            swap(tabl2[j],tabl2[i]);
            i++;
            j--;
        }
    }  while (i<=j);
    if (l<j) quick(tabl,tabl2,l,j);
    if (i<p) quick(tabl,tabl2,i,p);
}