Cod sursa(job #2374054)

Utilizator mirelPmirel p mirelP Data 7 martie 2019 16:44:40
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
struct IT
{
    int x,y;
}temp;
stack<int>st;

int n,m,i,j,k,viz[105];
vector<int>G[NMAX];
vector<int>dfs_discover,dfs_low,articulation_vertex,dfs_parent;
int ttime,dfsRoot,rootChildren;
vector< vector<int> > sol;

void Add(int tt, int fiu) {
    vector<int> step;
    while (st.top() != fiu) {
        step.push_back(st.top());
        st.pop();
    }
    step.push_back(fiu);
    step.push_back(tt);
    st.pop();
    sol.push_back(step);

}

void dfs(int u)
{
    int j;
    viz[u]=1;

    for(j=0;j<G[u].size();j++)
        if(viz[G[u][j]]==0)
        dfs(G[u][j]);
    st.push(u);
}
/*
void articulationPoint(int u)
{
    int v;
    ttime++;
    dfs_discover[u]=dfs_low[u]=ttime;
    for(int j=0;j<G[u].size();j++)
    {
        v=G[u][j];
        if(!dfs_discover[v])
        {
            dfs_parent[v]=u;
            if(u==dfsRoot)rootChildren++;
             temp.x=u;
             temp.y=v;
            st.push(v);
            articulationPoint(v);
            if(dfs_low[v]>=dfs_discover[u])
                {
                    articulation_vertex[u]=1;
                    Add(u,v);
                }
            dfs_low[u]=min(dfs_low[u],dfs_low[v]);
        }
        else
        {
            if(dfs_parent[u]!=v)
                dfs_low[u]=min(dfs_low[u],dfs_discover[v]);
        }
    }
}

*/
int main()
{

    int u,v;
    fin>>n>>m;


     //   for(j=1;j<=101;j++)viz[j]=0;
        for(i=1;i<=m;i++)
    {
        fin>>u>>v;
        G[u].push_back(v);

    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
    dfs(i);
    while(!st.empty())
    {
        fout<<st.top()<<" ";
        st.pop();
    }



    /*
    dfs_parent.assign(n+1,0);
    articulation_vertex.assign(n+1,0);
    dfs_discover.assign(n+1,0);
    dfs_low.assign(n+1,0);
    for(i=1;i<=n;i++)
    {
        if(dfs_discover[i]==0)
        {
            dfsRoot=i;
            rootChildren=0;
            articulationPoint(i);
            articulation_vertex[dfsRoot]=rootChildren>1;
        }
    }
    fout<<sol.size()<<endl;
  for (int i = 0; i <sol.size(); i++)
    sort(sol[i].begin(),sol[i].end());
        for (int i = 0; i <sol.size(); i++)
            {
            for(j=0;j<sol[i].size();j++)
            fout<<sol[i][j]<<" ";
            fout<<"\n";
}*/
    return 0;
}