Cod sursa(job #754307)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 1 iunie 2012 16:13:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

//stack<int> S;
vector<int> *Nod;
int N,M;
int cul[50001];
int res[50001];
int p;

void dfs(int i)
{
 cul[i] = 1;
 for (int j = 0;j < Nod[i].size();j += 1)
  {
   int k = Nod[i][j];
   if (cul[k] == 0)
     {
      dfs(k);
     }
  }
 res[p] = i;
 p += 1;
}

/*void dfs(int i)
{
 cul[i] = 1;
 S.push(i);
 while (S.size() > 0)
  {
   i = S.top();
   S.pop();
   if (cul[i] != 0)
     {
      continue;
     }
   cul[i] = 1;
   for (int j = 0;j < Nod[i].size();j += 1)
    {
     int k = Nod[i][j];
     if (cul[k] == 0)
       {
        S.push(k);
       }
    }
   res[p]
  }
}*/

int main(void)
{
 fstream fin("sortaret.in",ios::in);
 fstream fout("sortaret.out",ios::out);

 int i,a,b;
 Nod = new vector<int>[50001];

 fin >> N >> M;

 for (i = 0;i < M;i += 1)
  {
   fin >> a >> b;
   Nod[a].push_back(b);
  }

 p = 0;

 for (i = 1;i <= N;i += 1)
  {
   cul[i] = 0;
  }
 for (i = 1;i <= N;i += 1)
  {
   if (cul[i] == 0)
     {
      dfs(i);
     }
  }
 
 for (i = N - 1;i >= 0;i -= 1)
  {
   fout << res[i] << " ";
  }

 fin.close();
 fout.close();
 return 0;
}