Cod sursa(job #2107618)

Utilizator CozmaCatalinCozma Catalin CozmaCatalin Data 17 ianuarie 2018 16:24:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

ifstream in ("sortaret.in");
ofstream out ("sortaret.out");

const int MAX = 100005;


bool beenThere[MAX];

vector < int > myVector1[MAX];
vector < int > myVector2[MAX];
vector <  int > newVector[MAX];

int Timp[MAX];

int Count;
int Retin;
int Answer;

int N,M;
void Read()
{
    in >> N >> M;

    int x,y;
    while ( in >> x >> y)
    {
        myVector1[x].push_back(y);
        myVector2[y].push_back(x);
    }
}

void DFS(int Nod)
{
    beenThere[Nod] = true;

    for ( size_t i = 0 ; i < myVector1[Nod].size() ; ++i)
    {
        int Vecin = myVector1[Nod][i];
        if(beenThere[Vecin] == false)
        {
            beenThere[Vecin] = true;
            DFS(Vecin);
        }

    }
    Timp[++Count] = Nod;
}

void DFStranspus(int Nod)
{

    beenThere[Nod] = true;
newVector[Answer].push_back(Nod);

    for( size_t i = 0; i < myVector2[Nod].size() ; ++i)
    {
        int  Vecin = myVector2[Nod][i];

        if(beenThere[Vecin] == false)
        {

            DFStranspus(Vecin);

        }
    }




}
void Rezolv()
{
    for (int i = 1; i <= N ; ++i)
        if(beenThere[i] == false)
        DFS(i);

        for ( int i = 1; i <= N ; ++i)
            beenThere[i] = false;

            for ( int i = N ; i >= 1 ; --i)
            {
                if(beenThere[Timp[i]] == false)
                    {  Answer++;
                        DFStranspus(Timp[i]);

                    }


            }

          int ok = true;

       for ( int i = 1; i <= Answer; ++i)
              if(newVector[i].size() > 1)
              {
                  ok = false;
                  break;
              }


              if( ok == true )
                for ( int i = N; i >= 1 ; --i) out << Timp[i] <<" ";
}

int main()
{
    Read();
    Rezolv();



    return 0;
}