Pagini recente » Cod sursa (job #2716673) | Cod sursa (job #2136295) | Cod sursa (job #869262) | Cod sursa (job #806057) | Cod sursa (job #373133)
Cod sursa(job #373133)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on December 12, 2009, 11:32 AM
*/
#include <stack>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define InFile "sortaret.in"
#define OutFile "sortaret.out"
#define pb push_back
/*
*
*/
using namespace std;
vector< vector<int> > M;
vector< int > sol, grad;
bool *mark;
inline void DFS( int x )
{vector<int>::const_iterator it=M[x].begin(), iend=M[x].end();
mark[x]=true; //mark a visited
for( ; it < iend; ++it )
if( !mark[*it] )
DFS(*it);
sol.pb(x);
}
void solve( int n )
{vector<int>::const_iterator start, ending;
for( int i=0; i < n; ++i )
{
for( start=M[sol[i]].begin(), ending=M[sol[i]].end(); start < ending; ++start )
{
--grad[*start];
if( 0 == grad[*start] )
sol.pb(*start);
}
}
}
int main(int argc, char** argv)
{int n, m, x, y, i;
ifstream in(InFile);
in>>n>>m;
mark=(bool*)calloc( n+1, sizeof(bool) );
M.resize(n+1);
grad.resize(n+1);
while( m-- )
{
in>>x>>y;
++grad[y];
M[x].pb(y);
}/*
for( i=1; i <= n; ++i )
if( !mark[i] )
DFS(i);*/
for( i=1; i <= n; ++i )
if( 0 == grad[i] )
sol.pb(i);
solve(n);
ofstream out(OutFile);
copy( sol.begin(), sol.end(), ostream_iterator<int>(out, " ") );
free(mark);
return (EXIT_SUCCESS);
}