Pagini recente » Cod sursa (job #1933978) | Cod sursa (job #2774158) | Cod sursa (job #2733429) | Cod sursa (job #2258128) | Cod sursa (job #2798153)
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
class graf
{
private:
int n;
vector< int > vecini[100001];
int grad_int[100001];
int grad_ext[100001];
public:
graf(int n);
void citire_graf_orientat(int m);
void citire_graf_neorientat(int m);
void BFS(int start);
void DFS(int start, bool vizitat[]);
int nr_comp_conexe();
void sortare_topologica();
};
graf :: graf(int N)
{
n=N;
for(int i=1;i<=n;i++){
grad_int[i]=0;
grad_ext[i]=0;
}
}
void graf :: citire_graf_orientat(int M)
{
int a,b;
for(int i=1;i<=M;i++){
f>>a>>b;
grad_ext[a]++;
grad_int[b]++;
vecini[a].push_back(b);
}
}
void graf :: citire_graf_neorientat(int m)
{
int a,b;
for(int i=1;i<=m;i++){
f>>a>>b;
grad_ext[a]++;
grad_ext[b]++;
grad_int[a]++;
grad_int[b]++;
vecini[a].push_back(b);
vecini[b].push_back(a);
}
}
void graf :: BFS(int start)
{
queue <int> coada;
int distanta[n+1];
for(int i=1;i<=n;i++){
distanta[i]=-1;
}
coada.push(start);
distanta[start]=0;
while(coada.empty()==0){
for(int i=0;i<int(vecini[coada.front()].size());i++){
if(distanta[vecini[coada.front()][i]]==-1){
coada.push(vecini[coada.front()][i]);
distanta[vecini[coada.front()][i]]=distanta[coada.front()]+1;
}
}
coada.pop();
}
for(int i=1;i<=n;i++){
g<<distanta[i]<<" ";
}
}
int graf :: nr_comp_conexe()
{
bool vizitat[n+1];
int Nr=0;
for(int i=1;i<=n;i++){
vizitat[i]=0;
}
for(int i=1;i<=n;i++){
if(vizitat[i]==0){
Nr++;
DFS(i, vizitat);
}
}
return Nr;
}
void graf :: DFS(int start, bool vizitat[])
{
vizitat[start]=1;
for(int i=0;i<int(vecini[start].size());i++){
if(vizitat[vecini[start][i]]==0){
vizitat[vecini[start][i]]=1;
DFS(vecini[start][i],vizitat);
}
}
}
void graf :: sortare_topologica()
{
vector<int> rezolvare;
while(rezolvare.size()<n){
for(int i=1;i<=n;i++){
if(grad_int[i]==0){
rezolvare.push_back(i);
for(int j=0;j<int(vecini[i].size());j++){
grad_int[vecini[i][j]]--;
}
}
}
}
for(int i=0;i<n;i++){
g<<rezolvare[i]<<" ";
}
}
int n,m,S;
int main ()
{
f>>n>>m;
graf G(n);
//Rezolvare problema BFS
//f>>S;
//G.citire_graf_orientat(m);
//G.BFS(S);
//Rezolvare problema DFS - Componente Conexe
//G.citire_graf_neorientat(m);
//g<<G.nr_comp_conexe();
//Rezolvare Sortare Topologica
G.citire_graf_orientat(m);
G.sortare_topologica();
return 0;
}