Pagini recente » Istoria paginii runda/repost/clasament | Cod sursa (job #3172258) | Cod sursa (job #1528652) | Cod sursa (job #320467) | Cod sursa (job #1734440)
// folosesc o coada Q in care introduc pe rand nodurile care au gradul exterior zero
// complexitate O(N+M)
//100p (O(n+m))
#include <fstream>
#include <vector>
#define MAXN 50003
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
int x,i,j,n,m, k,C[MAXN], gri[MAXN];//gri[] gradul intern pentru fiecare nod
vector<int> G[MAXN];
void citire_graf(){
int i,x,y;
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y;
G[x].push_back(y);gri[y]++;
}
}
int main(void)
{
citire_graf();
for(i=1;i<=n;i++) //pun initial in coada nodurile de grad 0
if(gri[i]==0)C[++k]=i;
for(i=1;i<=k;i++) //parcurg coada
{
x=C[i];
for(j=0;j<G[x].size();j++)
{
gri[G[x][j]]--; //decrementez cu 1 toti succesorii directi a lui j
if(gri[G[x][j]]==0)C[++k]=G[x][j]; //cei ce au gradul 0 se pun in coada
}
}
for(i=1;i<=k;i++)fo<<C[i]<< " ";
return 0;
}
//#include <fstream>//60p (O(n^2)) timp depasit
//#include <vector>
//#define MAXN 50003
//using namespace std;
//ifstream fi("sortaret.in");
//ofstream fo("sortaret.out");
//int n,m, viz[MAXN], gri[MAXN];//gri[] gradul intern pentru fiecare nod
//vector<int> G[MAXN];
//
//void citire_graf(){
// int i,x,y;
// fi>>n>>m;
// for(i=1;i<=m;i++)
// {
// fi>>x>>y;
// G[x].push_back(y);gri[y]++;
// }
//}
//
//int main(void)
//{
// citire_graf();
// int i, j, k;
// //se sfiseaza nodurile (j) care la un moment dat un gradul interior zero. ("radacinile")
// //apoi "stergem" arcele ce ies din (j) decrementam toate nodurile (succesorii directi a lui j)
// //si repetam in continuare pe graful ramas.
// for(i = 1; i <= n; i++) //repet operatia de mai sus de n ori
// {
// for(j = 1; j <= n; j++) //parcurg nodurile grafului
// if(!viz[j] && gri[j] == 0) //daca gasesc un nod j nevizitat si de grad intern egal cu 0
// {
// viz[j]=1; fo<<j<<" "; //afisez j
// for(k=0;k<G[j].size();k++) //decrementez cu 1 toti succesorii directi a lui j
// gri[G[j][k]]--;
// break ; // ies !!!
// }
// }
// return 0;
//}