Pagini recente » Cod sursa (job #1557190) | Cod sursa (job #2057761) | Cod sursa (job #1680597) | Cod sursa (job #449360) | Cod sursa (job #2796831)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
class Graf{
public:
Graf(){}
void citire_dfs()
{
in>>m_nrNoduri>>m_nrMuchii;
for(int i=0;i<m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
m_list[y].push_back(x);
}
}
void bfs()
{
in>>m_nrNoduri>>m_nrMuchii>>m_start;
for(int i=0;i<m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
}
for(int i=1;i<=m_nrNoduri;i++)
{
m_viz[i]=2000000000;
}
m_viz[m_start]=0;
m_q[1]=m_start;
int p=1;
int u=1;
while(p<=u) //<=
{
int r=m_q[p];
for(int i=0;i<(m_list[r].size());i++)
{
int e=m_list[r][i];
// cout<<e<<' ';
if(m_viz[r]+1<m_viz[e])
{
m_viz[e]=m_viz[r]+1;
u++;
m_q[u]=e;
}
}
p++;
}
for(int i=1;i<=m_nrNoduri;i++)
{
if(m_viz[i]!=2000000000)
out<<m_viz[i]<<' ';
else
out<<"-1 ";
}
}
void r_dfs(int q)
{
m_viz[q]=1;
for(int i=0;i<m_list[q].size();i++)
{
int r=m_list[q][i];
if(m_viz[r]==0)
{
r_dfs(r);
}
}
}
void dfs()
{
in>>m_nrNoduri>>m_nrMuchii;
for(int i=0;i<m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
m_list[y].push_back(x);
}
int s=0;
for(int i=1;i<=m_nrNoduri;i++)
{
if(m_viz[i]==0)
{
r_dfs(i);
s++;
}
}
r_dfs(1);
out<<s<<'\n';
}
void sorttop_recursie(int q)
{
int i;
m_viz[q]=1;
for(i=0;i<m_list[q].size();i++)
{
int t=m_list[q][i];
if(m_viz[t]==0)
{
sorttop_recursie(t);
}
}
m_aux++;
m_ordtop[m_aux]=q;
}
void sorttop()
{
int i;
in>>m_nrNoduri>>m_nrMuchii;
for(i=0;i<m_nrNoduri;i++)
{
m_grad.push_back(0);
m_ordtop.push_back(0);
}
for(i=1;i<=m_nrMuchii;i++)
{
int x,y;
in>>x>>y;
m_list[x].push_back(y);
m_grad[y]++;
}
for(i=1;i<=m_nrNoduri;i++)
{
if(m_grad[i]==0 && m_viz[i]==0)
{
sorttop_recursie(i);
}
}
//cout<<w<<'\n';
for(i=m_aux;i>0;i--)
{
out<<m_ordtop[i]<<' ';
}
}
private:
int m_nrMuchii;
int m_nrNoduri;
int m_start;
int m_viz[100001];
int m_q[100001];
vector<int> m_ordtop;
vector<int> m_grad;
int m_aux;
vector<int> m_list[100001];
};
int main() {
Graf graf;
graf.sorttop();
}