Pagini recente » Cod sursa (job #3336502) | Cod sursa (job #1879791) | Cod sursa (job #2122199) | Cod sursa (job #3262732) | Cod sursa (job #3342400)
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream cin("topsort.in");
ofstream cout ("topsort.out");
int n,x,y,nrniv,m;
vector<int>g[NMAX];
vector<int>niv[NMAX];
int di[NMAX];
void citire()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{cin>>x>>y;
///daca am arc de la x la y
g[x].push_back(y);
di[y]++;
}
}
void descompunere_pe_niveluri()
{
int total=0;
while (total<n) ///ai am varfuri de reartizat pe niveluri
{
///pe nivelul curent plasam toate varfurile x cu di[x]=0
for (int x=1; x<=n; x++)
if (di[x]==0)
niv[nrniv].push_back(x);
///pentru tate varfurile de pe nivelul curent trebuie sa le elimin logic si sa decrementez di pentru vecnii lor
for (int i=0; i<niv[nrniv].size(); i++)
{
x=niv[nrniv][i];
di[x]=-1; ///l am eliminat logic
///parcurg lista de adiacenta a lui x
for (int j=0; j<g[x].size(); j++)
di[g[x][j]]--;
}
total+=niv[nrniv].size();
nrniv++;
}
}
void afisare()
{
//cout<<nrniv<<endl;
for (int i=0;i<nrniv;i++)
{
for (int j=0;j<niv[i].size();j++)
cout<<niv[i][j]<<' ';
cout<<endl;
}
}
int main()
{
citire();
descompunere_pe_niveluri();
afisare();
return 0;
}