Pagini recente » Cod sursa (job #1011175) | Cod sursa (job #1188228) | Cod sursa (job #1204009) | Cod sursa (job #1675742) | Cod sursa (job #589925)
Cod sursa(job #589925)
/*
bfs, dar in loc sa pun in coada vecinii nodului curent (si sa-i
marchez ca vizitati), retin un contor cu cati tati mai am de adaugat
ai fiecarui nod si in bfs micsorez contorul. pun in coada doar cand
contorul ii ajunge la 0.
*/
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 50005;
int n;
vector<int> fiu[N];
int contor_pred[N]={0};
bool are_tata[N];
queue<int> coada;
int sol[N],nsol=0;//nodurile in ordinea parcursa;
void citire()
{
int a,b,m;
scanf("%d %d",&n,&m);
for (int i = 1; i <= m; ++i)
{
scanf("%d %d",&a,&b);
fiu[a].push_back(b);
++contor_pred[b];
are_tata[b] = true;
}
}
void bfs_cu_contoruri()
{
int nod,dest;
//golire coada, nu este necesara
for (int i = 1; i <= n; ++i)//pun in coada nodurile fara tati
if (!are_tata[i])
coada.push(i);
while (!coada.empty())
{
nod = coada.front();
sol[++nsol] = nod;
for (unsigned int i = 0; i < fiu[nod].size(); ++i)
{
dest = fiu[nod][i];
--contor_pred[dest];
if (contor_pred[dest] == 0)
coada.push(dest);
}
coada.pop();
}
}
void scriere()
{
for (int i = 1; i <= n; ++i)
printf("%d ",sol[i]);
}
int main()
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
citire();
bfs_cu_contoruri();
scriere();
return 0;
}