Cod sursa(job #340769)

Utilizator alexandru92alexandru alexandru92 Data 16 august 2009 15:12:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#define Nmax 111
using namespace std;
ifstream in;
ofstream out;
vector<int> list[Nmax];
vector<int> v;
bitset<Nmax> uz;
stack<int> st;
int main()
{int N,M,x,y,i,it,length;
    in.open("sortaret.in");
    in>>N>>M;
    while( M-- )
    {
        in>>x>>y;
        list[x].push_back(y);
    }
    for( i=1; i<=N; ++i )
      if( !uz[i] )
      {
          if( list[i].empty() )
          {
              v.push_back(i);
          }
          else {
                    st.push(i);
                    while( !st.empty() )
                    {
                        x=st.top(); st.pop(); v.push_back(x);
                        for( length=list[x].size(),it=0; it<length; ++it )
                          if( !uz[list[x][it]] )
                          {
                              uz.flip(list[x][it]); st.push(list[x][it]);
                          }
                    }
                }
      }
    out.open("sortaret.out");
    copy( v.begin(), v.end(), ostream_iterator<int>(out," ") );
    return 0;
}