Cod sursa(job #2796898)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 8 noiembrie 2021 23:18:10
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.15 kb
#include<bits/stdc++.h>
using namespace std;

const int inf=(1e9);

const int dim=(1e5);

char buff[dim+5];

int pos=0;

int cnt[7505];

void read(int &nr)
{
    int semn=1;
    nr=0;


    while(!isdigit(buff[pos]))
    {

        if(buff[pos]=='-') semn=-1;

        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }


    }


    while(isdigit(buff[pos]))
    {
        nr=nr*10+buff[pos]-'0';
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }

    nr*=semn;

}

class Graph
{

private:

    int m_nodes;

    vector< vector< pair<int,int> > > m_adjList;

    vector<pair<int, pair<int,int> > > m_edges;

    vector<bool> m_visited;


    bool m_areLabeled;

public:

    Graph(int nodes,bool areLabeled)
    {
        m_nodes=nodes;
        m_areLabeled=areLabeled;

        m_adjList.resize(nodes+5);

    }


    void addEdge(int from, int to, int cost=0)
    {
        m_adjList[from].push_back(make_pair(to,cost));
        m_edges.push_back(make_pair(from,make_pair(to,cost)));
    }

    void resetVisited()
    {
        m_visited.resize(m_nodes+5);

        for(int i=0;i<=m_nodes;i++)
            m_visited[i]=0;
    }


    vector<int> bfs(int source)
    {
        deque<int> q;

        vector<int> distances(m_nodes+5,-1);

        distances[source]=0;

        q.push_back(source);


        while(!q.empty())
        {
            int current = q.front();

            q.pop_front();

            for(auto it: m_adjList[current])
            {
                if(distances[it.first]==-1)
                {
                    distances[it.first]=1+distances[current];
                    q.push_back(it.first);
                }
            }

        }


        return distances;

    }

    void dfs(int node)
    {
        m_visited[node]=1;

        for(auto it:m_adjList[node])
        {
            if(m_visited[it.first]) continue;
            dfs(it.first);
        }
    }

    int getCC()
    {

        resetVisited();

        int ans=0;
        for(int i=1;i<=m_nodes;i++)
            if(!m_visited[i]) dfs(i),ans++;


        return ans;
    }


    void tarjan(vector<bool>& inStack, vector<int>& st,vector<int>& lvl, vector<int>& low, vector<vector<int> > &solution, int node,int fat,int& currentLevel)
    {
        low[node] = lvl[node] = ++currentLevel;
        st.push_back(node);

        inStack[node]=1;

        for(auto it:m_adjList[node])
        {
            if(!lvl[it.first])
            {
                tarjan(inStack,st,lvl,low,solution,it.first,node,currentLevel);
                low[node] = min(low[node],low[it.first]);
            }
                else

            if(inStack[it.first])
            {
                low[node] = min(low[node],low[it.first]);
            }
        }


        if(low[node] == lvl[node])
        {
            solution.push_back({});
            int x = -1;

            while(x!=node)
            {
                x = st.back();
                solution.back().push_back(x);
                inStack[x]=0;
                st.pop_back();
            }
        }

    }


    vector<vector<int> > getSCCs()
    {
        vector<vector<int> > solution;
        vector<int> lvl(m_nodes+5,0);
        vector<int> low(m_nodes+5,0);
        vector<int> st;
        vector<bool> inStack(m_nodes+5,0);
        int currentLevel = 0;

        for(int i=1;i<=m_nodes;i++)
            if(!lvl[i])
                tarjan(inStack,st,lvl,low,solution,i,0,currentLevel);

        return solution;
    }

    void bicoDFS(vector<vector<int> >& solution, vector<int>& st,vector<bool>& seen, vector<int>& lvl, vector<int>& low, int node,int fat, int currentLevel)
    {
        st.push_back(node);
        low[node]=lvl[node]=currentLevel;
        seen[node]=1;


        for(auto it:m_adjList[node])
        {
            if(it.first==fat) continue;

            if(seen[it.first])
            {
                low[node] = min(low[node],lvl[it.first]);
                continue;
            }


             bicoDFS(solution,st,seen,lvl,low,it.first,node,currentLevel+1);

            low[node] = min(low[node],low[it.first]);

            if(low[it.first]>=lvl[node])
            {
                solution.push_back({});
                int x=0;

                do
                {
                    x = st.back();
                    solution.back().push_back(x);
                    st.pop_back();
                }while(x!=it.first);

                solution.back().push_back(node);
               // exit(0);
            }

        }
    }
    vector<vector<int> > getBiconected()
    {
        vector<vector<int> > solution;
        vector<int> lvl(m_nodes+5,0);
        vector<int> low(m_nodes+5,0);
        vector<int> st;
        vector<bool> seen(m_nodes+5,0);

        bicoDFS(solution,st,seen,lvl,low,1,0,1);

        return solution;

    }

    void topSort(vector<int>& solution, vector<bool>& seen, int node,int fat)
    {

        seen[node]=1;

        for(auto it:m_adjList[node])
        {
            if(seen[it.first]) continue;
            if(it.first==fat) continue;

            topSort(solution,seen,it.first,node);
        }

        solution.push_back(node);
    }
    vector<int> getTopSort()
    {
        vector<int> solution;
        vector<bool> seen(m_nodes,0);

        for(int i=1;i<=m_nodes;i++)
            if(!seen[i])
                topSort(solution,seen,i,0);

        reverse(solution.begin(),solution.end());

        return solution;
    }
};


int main()
{

    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    int n,m,x,y;

    scanf("%d%d",&n,&m);

    Graph G(n,1);

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        G.addEdge(x,y);
    }

    vector<int> solution = G.getTopSort();


    for(auto it:solution)
        printf("%d ",it);

    printf("\n");


    return 0;
}