Cod sursa(job #2907087)

Utilizator MoraruLiviuMoraru Mihai-Liviu MoraruLiviu Data 28 mai 2022 18:02:42
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.13 kb
#include<bits/stdc++.h>

using namespace std;


//ifstream fin("bfs.in");
//ofstream fout("bfs.out");

//ifstream fin("dfs.in");
//ofstream fout("dfs.out");

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

//struct edge{
//    int x, y;
//    edge(int x1, int y1){
//        x=x1;
//        y=y1;
//    }
//    edge(){}
//};

class Graph{
private:
    int N, M;
    bool is_directed, has_costs;
    vector<vector<int>> adjacency_list;

public:
    Graph(int N, int M, bool is_directed, bool has_costs);
    void Add_edge(int x, int y);

    void bfs(queue<int> &q, vector<bool> &visited, vector<int> &distance);
    vector<int> bfs_distance(int x);
    void dfs(int x, vector<bool> &visited);
    //void dfc_bcc(int x, vector<int> &discovery_time, vector<int> &low, stack<pair<int, int>> &)
    vector<set<int>> Biconnected();
    vector<set<int>> Componente_Tare_Conexe();
    void Topological_Sort(int x, vector<bool>& visited, vector<int>& sorted);
    vector<vector<int>> Muchii_critice();

};

    Graph::Graph(int N, int M, bool is_directed, bool has_costs){
        this->N = N;
        this->M = M;
        this->is_directed = is_directed;
        this->has_costs = has_costs;
        adjacency_list.resize(N+1);
    }

    void Graph::Add_edge(int x, int y){
        adjacency_list[x].push_back(y);
        if(!is_directed)
            adjacency_list[y].push_back(x);
    }

    void Graph::bfs(queue<int> &q, vector<bool> &visited, vector<int> &distance){

        while(!q.empty()){
            int current_node = q.front();
            for(int i=0; i<adjacency_list[current_node].size(); i++){
                if(!visited[adjacency_list[current_node][i]]){
                    q.push(adjacency_list[current_node][i]);
                    visited[adjacency_list[current_node][i]] = true;
                    distance[adjacency_list[current_node][i]] = distance[current_node]+1;
                }
            }
            q.pop();
        }

    };

    vector<int> Graph::bfs_distance(int x){
        queue<int> q;
        vector<bool> visited(N+1);
        vector<int> distance(N+1, -1);

        q.push(x);
        visited[x] = true;
        distance[x] = 0;
        bfs(q, visited, distance);
        return distance;
    };


void BFSInfoarena(){
    int N,M,S;
    fin>>N>>M>>S;
    Graph g(N,M,true,false);
    int x, y;
    for(int i=0; i<M; i++){
        fin >> x >> y;
        g.Add_edge(x, y);
    }
    vector<int> rezolvare = g.bfs_distance(S);
    for(int i = 1; i < rezolvare.size(); i++){
        fout<<rezolvare[i]<<" ";
    }
}


    void Graph::dfs(int x, vector<bool> &visited){
        visited[x] = true;
        for(int i = 0; i < adjacency_list[x].size(); i++){
            if (!visited[adjacency_list[x][i]]){
                dfs(adjacency_list[x][i], visited);
            }
        }
    }

void DFSInfoarena(){
    int N,M;
    fin>>N>>M;
    Graph g(N,M,false,false);
    vector<bool> visited(N+1);

    int x,y;
    for(int i = 0; i < M; i++){
        fin>>x>>y;
        g.Add_edge(x, y);
    }

    int counter = 0;
    for(int i = 1; i <= N; i++){
        if(!visited[i]){
            g.dfs(i, visited);
            counter++;
        }
    }

    fout<<counter;
}



    void Graph::Topological_Sort(int x, vector<bool>& visited, vector<int>& sorted){
        visited[x] = true;
        for(int i=0; i<adjacency_list[x].size(); i++){
            if (!visited[adjacency_list[x][i]])
                Topological_Sort(adjacency_list[x][i], visited, sorted);
        }
        sorted.push_back(x);
    }

void SortaretInfoarena(){
    int N,M;
    fin>>N>>M;
    Graph g(N,M,true,false);

    int x,y;
    for(int i = 0; i < M; i++){
        fin>>x>>y;
        g.Add_edge(x, y);
    }

    vector<bool> visited(N+1);
    vector<int> sorted;
    for(int i = 1; i <= N; i++){
        if(!visited[i])
            g.Topological_Sort(i, visited, sorted);
    }
    for(int i =  sorted.size()-1; i > -1; i--){
        fout<<sorted[i]<<" ";
    }
}



int main()
{
    SortaretInfoarena();
    return 0;
}