Cod sursa(job #2790415)

Utilizator oporanu.alexAlex Oporanu oporanu.alex Data 28 octombrie 2021 22:20:54
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.46 kb
#include <bits/stdc++.h>

using namespace std;

const int vmax = 100005;
stack<int> st;

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

queue <int> q;
class Graph{
public:
    int noduri, muchii;
    vector<int> adj[vmax];
    bool vis[vmax];
    Graph(int _noduri, int _muchii): noduri(_noduri), muchii(_muchii){
        q = queue<int>();
    }

    virtual void build() = 0;
    virtual void bfs(int source) = 0;
    virtual void dfs(int node) = 0;
    virtual void sol() = 0;
    virtual long long getCconexe() = 0;
    virtual void sortareTopologica() = 0;
    virtual void dfsTopologic(int) = 0;
};

class OrientedGraph : public Graph{
     int dist[vmax];
public:
    OrientedGraph(int _noduri, int _muchii): Graph(_noduri, _muchii){
            for(int i = 1; i <= noduri; ++i)
                {
                    dist[i] = -1;
                    vis[i] = false;
                }
    }

    virtual void build() override{
        for(int i = 0; i < muchii; ++i){
            int x, y;
            in >> x >> y;
            adj[x].push_back(y);
            }
        }
    void bfs(int source) override{
        q.push(source);
        dist[source] = 0;
        while(!q.empty())
        {
            int crt = q.front();
            q.pop();
            for(unsigned i = 0; i < adj[crt].size(); ++i)
                {
                    if(dist[adj[crt][i]] == -1)
                        {
                            dist[adj[crt][i]] = 1 + dist[crt];
                            q.push(adj[crt][i]);
                        }
                }
        }
    }
    virtual void dfs(int node) override{}

    virtual long long getCconexe() override{}

    virtual void dfsTopologic(int node) override{
        vis[node] = true;
        for(unsigned i = 0; i < adj[node].size(); ++i)
            if(!(vis[adj[node][i]]))
                dfsTopologic(adj[node][i]);
        st.push(node);
    }



    virtual void sortareTopologica() override{
        for(int i = 1; i <= noduri; ++i)
            if(!(vis[i]))
                dfsTopologic(i);
    }


    virtual void sol()  override{
        this->sortareTopologica();
        while(st.size()){
            out << st.top() << ' ';
            st.pop();
        }
    }
};

class UnorientedGraph : public Graph{
public:
    UnorientedGraph(int _noduri, int _muchii) : Graph(_noduri, _muchii){}
    virtual void build() override{
        for(int i = 0; i < muchii; ++i)
        {
            int x, y;
            in >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    }

    virtual void dfs(int node) override{
        vis[node] = true;
        for(unsigned i = 0; i < adj[node].size(); ++i)
            if(!(vis[adj[node][i]]))
                dfs(adj[node][i]);
    }

    void bfs(int source) override{
    }

    virtual long long getCconexe() override{
        long long cnt = 0;
        for(int i = 1; i <= noduri; ++i)
            if(!(vis[i]))
            {
                ++cnt;
                dfs(i);
            }
        return cnt;
    }
    virtual void dfsTopologic(int node){}
    virtual void sortareTopologica() override{}

    virtual void sol() override{
        out << this->getCconexe();
    }


};

int main()
{
    int N, M, S;
    in >> N >> M;
    Graph* g = new OrientedGraph(N, M);
    g->build();
    g->sol();

    delete g;
    return 0;

}