Pagini recente » Cod sursa (job #427894) | Cod sursa (job #1649318) | Cod sursa (job #1791804) | Cod sursa (job #186660) | Cod sursa (job #2786083)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
class Graph{
private:
int n;
vector < vector<int> > la;
void dfs(int nod_crt, vector<bool> &viz);
public:
Graph(int nr_noduri):n(nr_noduri), la(nr_noduri+1){}
~Graph() = default;
void add_edge(int from, int to){
la[from].push_back(to);
}
void bfs_print_dist(int start);
int nr_conexe_dfs();
void print_sortare_topologica();
};
void Graph::bfs_print_dist(int start){
vector<int> dist(n+1,0);
queue<int> q;
int nod_crt;
q.push(start);
dist[start]=1;
while(!q.empty())
{
nod_crt = q.front();
q.pop();
for(auto nod_vecin: la[nod_crt])
{
if(dist[nod_vecin] == 0)
{
dist[nod_vecin] = dist[nod_crt] + 1;
q.push(nod_vecin);
}
}
}
for(int i=1;i<=n;++i)
g<<dist[i]-1<<' ';
}
int Graph::nr_conexe_dfs(){
vector<bool> viz(n+1, false);
int nr_c=0;
for(int i=1;i<=n;++i)
{
if(!viz[i])
{
++nr_c;
dfs(i, viz);
}
}
return nr_c;
}
void Graph::print_sortare_topologica()
{
queue<int> zero_nodes;
int grades[n+1] = {0}, i;
int nod_curent;
for(i=1;i<=n;++i)
{
for(auto nod_vecin: la[i])
++grades[nod_vecin];
}
for(i=1; i<=n;++i)
if(grades[i] == 0)
zero_nodes.push(i);
if(zero_nodes.empty())
{
cout<<"Cyclic Graph. Can't sort.";
return;
}
while(!zero_nodes.empty())
{
nod_curent = zero_nodes.front();
zero_nodes.pop();
g<<nod_curent<<' ';
for(auto nod_vecin: la[nod_curent])
{
--grades[nod_vecin];
if(grades[nod_vecin] == 0)
zero_nodes.push(nod_vecin);
}
}
}
void Graph::dfs(int nod_crt, vector<bool> &viz){
for(auto nod_vecin: la[nod_crt])
{
if(!viz[nod_vecin])
{
viz[nod_vecin] = true;
dfs(nod_vecin, viz);
}
}
}
int main()
{
int n,m;
int a,b;
f>>n>>m;
Graph gr(n);
for(int i=0;i<m;++i)
{
f>>a>>b;
gr.add_edge(a,b);
}
gr.print_sortare_topologica();
return 0;
}
/*
4 5 0 2 3 1
4 5 2 3 1 0
4 5 2 0 3 1
4 5 2 3 0 1
5 4 2 3 1 0
5 4 0 2 3 1
5 2 4 3 1 0
5 2 4 0 3 1
5 2 4 3 0 1
5 2 3 4 1 0
5 2 3 4 0 1
*/