Pagini recente » Cod sursa (job #214924) | Cod sursa (job #273514) | Cod sursa (job #1395943) | Cod sursa (job #349984) | Cod sursa (job #1734444)
//var III
// parcurgere in adancime pentru a calcula timpii de terminare pentru fiecare varf
// 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,viz[MAXN], sol[MAXN];
vector<int> G[MAXN];
void DF(int nod){
int i;
viz[nod]=1;
for(i=0;i<G[nod].size();i++)
if(viz[G[nod][i]]==0)DF(G[nod][i]);
sol[++k]=nod;
}
void citire_graf(){
int i,x,y;
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y;
G[x].push_back(y);
}
}
int main(void)
{
citire_graf();
for(i=1;i<=n;i++)
if(viz[i]==0)DF(i);
for(i=k;i>=1;i--)fo<<sol[i]<< " ";
//for(i=1;i<=n;i++) //afis liste de adiacenta
//{
// fo<<i<<" -> ";
// for(j=0;j<G[i].size();j++)fo<<G[i][j]<<" ";
// fo<<endl;
//}
return 0;
}
////var II
//// 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;
//}
//var I
////60p (O(n^2)) timp depasit
//#include <fstream>
//#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;
//}