iza

    //kolory kolorowania grafu:
    //biały - 0 ; szaro - 1; czarno - 2
    //0 - drzewowa, 1- wsteczna, 2- poprzeczna / wyprzedzajaca
#include <utility>
#include <iostream>
#include <list>
#include <vector>

#define data int

    using namespace std;
        vector<int> * visited;
        vector<int> * timeT;
        int time = 0; //  ile razy

    using namespace std;

                struct node{
                        data d;
                        vector<node*>  next;
                                };

                class graph {
                        private:

                                int count;
                                vector<node> * nodes;
                        public:
                                list <pair<int,int> > F; // forward - wyprzedzająca
                                list <pair<int,int> > B; // backward - wsteczna
                                list <pair<int,int> > T; // tree - drzewowa
                                list <pair<int,int> > C;// crossing - poprzeczna
                        graph(int numOfNods) {  // konstruktor
                                visited = new vector<int>(numOfNods);
                                count = numOfNods;
                                nodes  = new vector<node>(numOfNods);
                                timeT = new vector<int>(numOfNods);
                                for(int i=0;i<numOfNods;i++){   //numerujemy wierzcholki
                                        (*nodes)[i].d=i+1;
                                }
                                for(int i=0; i<count;i++){
                                    (*visited)[i]==0;    //malujemy graf na bialo  (nieodwiedzone)
                                }
                        }
                        ~graph(){       //destruktor
                                delete nodes;
                                delete visited;
                                delete timeT;
                        }

                        int first(int v){
                                v=v-1;
                                if(v<count && v>= 0)
                                {
                                                if((*nodes)[v].next.size()<1) return -1;
                                        if(((*nodes)[v].next[0]) != NULL)
                                        {
                                                return (*(*nodes)[v].next[0]).d;
                                        }
                                }
                                        return -1;
                        }

                        int next(int v, int i){
                                i=i-1;
                                if(v-1>=count || v-1<0 ){
                                        return -1;
                                }
                                node * n  = &(*nodes)[v-1];
                                if((n->next.size())>i+1){
                                    node * next= (n->next[i+1]);
                                    return next->d;
                                }
                                return -1;
                        }


                        node* vertex(int v, int i){
                                    v=v-1;
                                node  n  = (*nodes)[v];
                                for(int j=0;j<n.next.size();j++){
                                        if((*n.next[j]).d==i) return n.next[j];
                                                                }
                                        return NULL;
                                                }

                        void setEdge(int v, int i)
                        {
                                v=v-1;
                            i=i-1;
                            (*nodes)[v].next.push_back(&(*nodes)[i]);
                        }

                         vector<node>  getNodes(){
                            return *nodes;
                        }

                        void printF(){
                            cout<<"Krawedzie wyprzedzajace: "<<endl;
                            for (list <pair<int,int> >::iterator it=F.begin(); it != F.end(); ++it)
                                cout << ' '<< get<0>(*it)<<" -> "<<get<1>(*it)<<endl;
                        }
                        void printT(){
                            cout<<"Krawedzie drzewowe: "<<endl;
                            for (list <pair<int,int> >::iterator it=T.begin(); it != T.end(); ++it)
                                cout << ' '<< get<0>(*it)<<" -> "<<get<1>(*it)<<endl;
                        }
                        void printB(){
                            cout<<"Krawedzie wsteczne: "<<endl;
                            for (list <pair<int,int> >::iterator it=B.begin(); it != B.end(); ++it)
                                cout << ' '<< get<0>(*it)<<" -> "<<get<1>(*it)<<endl;
                        }
                        void printC(){
                            cout<<"Krawedzie poprzeczne: "<<endl;
                            for (list <pair<int,int> >::iterator it=C.begin(); it != C.end(); ++it)
                                cout << ' '<< get<0>(*it)<<" -> "<<get<1>(*it)<<endl;
                        }
                };




// przeglądanie DFS:

        void DFS(int v,graph * g){
            //cout<<"dfs :"<<v<<"\n";
            v=v-1;
            (*visited)[v] = 1; //kolorujemy na szaro
            (*timeT)[v]=++time;
            vector<node> nodes = g->getNodes();
            for(int i=0;i<nodes[v].next.size();i++){

                node * next = (nodes[v].next[i]);

                if (next!=NULL)  { //przegladamy jaki jest kolor sasiedniego wierzcholka

                    if((*visited)[next->d -1]==0){
                        g->T.push_back(pair<int,int>(v+1, next->d));   // drzewowa
                        DFS(next->d,g);

                    }
                    else if ((*visited)[next->d -1]==1){
                            g->B.push_back(pair<int,int>(v+1, next->d));  //wsteczna

                    }
                    else if ((*visited)[next->d -1] ==2 ){  //czarny, odwiedzony

                            if((*timeT)[next->d -1] > (*timeT)[v]){
                                g->F.push_back(pair<int,int>(v+1, next->d));

                            }
                            else {
                                g->C.push_back(pair<int,int>(v+1, next->d));

                            }

                    }

                }

            }
            (*visited)[v]=2;
            //cout<<"wyszlo dfs "<<v+1<<"\n";
        }



int main(int argc, char** argv) {

        int nodeCount = 0;
        int i=0,v = 0;
        cout << "Podaj liczbe wierzcholkow: ";
        cin >> nodeCount ;
        graph g(nodeCount);
        cout << "Podaj krawedzie pomiedzy wierzcholkami (dwie liczby oddzielone spacja)."<< endl;
        cout << "Aby zakonczyc wpisywanie podaj wierzcholek 0 "<< endl;
        do{
                cin>>v;
                if(v!=0){
                    cin>>i;
                    g.setEdge(v,i);
                }
        }while( v != 0 );

        cout << "Wierzcholki grafu maja sasiadow: "<<endl;
        for (int i = 1; i<= nodeCount; i++)
        {
                cout << "wierzcholek nr " << i << " ma sasiadow: ";
                int j=1;
                if(g.first(i) != -1) {
                                cout<<g.first(i)<<" ";
                        while ( g.next(i, j) != -1)
                        {
                                cout << g.next(i, j) << " " ;
                                j++;
                        }

                }
                                cout<< endl;
        }
        cout << "Przegladanie grafu od wierzcholka numer 1: "<< endl;
       DFS(1,&g);
       g.printT();
       g.printB();
       g.printC();
       g.printF();


        cout << "Przegladanie grafu od wierzcholka numer 6: "<< endl;
       DFS(6,&g);
       g.printT();
       g.printB();
       g.printC();
       g.printF();

        return 0;
}