Cod sursa(job #2919333)

Utilizator utilizator20052022utilizatorr utilizator20052022 Data 16 august 2022 19:11:16
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.71 kb
#include <iostream>
#include<fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

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

class Graph{
private:
    int n_nodes;
    vector<vector<int>> adj;
    vector<pair< int , pair<int,int>> > adj_weight;
public:
    Graph(){
        n_nodes = 0;
        adj = {};
    }
    Graph(int n, vector<vector<int>> &gr){
        n_nodes = n;
        adj = gr;
    }

    void dfs(int node, vector<bool> &visited, vector<vector<int>> &gr);
    void dfs_sort_top(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution);
    void dfs_comp_conexe(int node, vector<bool> &visited, vector<vector<int>> &gr, int &cnt);
    void bfs(int node, vector<bool> &visited, vector<vector<int>> &gr);

    void solve_sort_top();
    void solve_comp_conexe();
    void solve_bfs(int node);
    void solve_ctc();
};

//algorithms

void Graph:: dfs(int node, vector<bool> &visited, vector<vector<int>> &gr){
    visited[node] = true;
    for(auto &x: gr[node]){
        if(!visited[x]) dfs(x, visited, gr);
    }
}

void Graph:: dfs_sort_top(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution){
    visited[node] = true;
    for(auto &x: gr[node]){
        if(!visited[x]) dfs_sort_top(x, visited, gr, solution);
    }
    solution.push_back(node);
}

void Graph:: bfs(int node, vector<bool> &visited, vector<vector<int>> &gr){
    queue<int> q;
    vector<int> d(n_nodes+1, -1);
    visited[node] = true;
    d[node] = 0;
    q.push(node);
    while(!q.empty()){
        for(auto x: gr[q.front()]){
            if(!visited[x]){
                visited[x] = true;
                d[x] = d[q.front()] + 1;
                q.push(x);
            }
        }
        q.pop();
    }

    for(int i = 1; i <= n_nodes; ++i) //cout<<d[i]<<' ';
        fout<<d[i]<<' ';
}

//solve functions

void Graph::solve_sort_top(){
    vector<bool> v(n_nodes+1, false);
    vector<int> sol(n_nodes+1);

    for(int i = 1; i <= n_nodes; ++i){
        if(!v[i]) dfs_sort_top(i, v, adj, sol);
    }
    reverse(sol.begin(), sol.end());
    for(int i = 0; i < n_nodes; ++i)
        //cout<<sol[i]<<' ';
        fout<<sol[i]<<' ';
}

void Graph::solve_comp_conexe(){
    vector<bool> v(n_nodes+1, false);
    int ans = 0;

    for(int i = 1; i <= n_nodes; ++i){
        if(!v[i]){
            dfs(i, v, adj);
            ans++;
        }
    }

    fout<<ans<<' ';
}

void Graph::solve_bfs(int node){
    vector<bool> v(n_nodes+1, false);
    bfs(node, v, adj);
}

void Graph::solve_ctc(){
    //Kosaraju
    vector<bool> v(n_nodes+1, false);
    vector<int> order;
    vector<vector<int>> solution;

    for (int i=1; i<= n_nodes; i++){
        if (!v[i])  dfs_sort_top(i, v, adj, order);
    }

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

    vector<vector<int>> transposed_graph(n_nodes+1);

    for(int i = 1; i <= n_nodes; ++i){
        v[i] = false;
        for(auto x: adj[i]){
            transposed_graph[x].push_back(i);
        }
    }

    for (auto &x: order){
        if (!v[x]){
            vector < int > aux;
            dfs_sort_top(x, v, transposed_graph, aux);
            solution.push_back(aux);
        }
    }

    //cout<<(int)solution.size()<<'\n';
    fout<<(int)solution.size()<<'\n';
    for(auto x: solution){
        for(auto y: x) fout<<y<<' ';
        fout<<'\n';
            //cout<<y<<' ';
        //cout<<'\n';
    }


}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, x, y;
    //cin>>n>>m;
    fin>>n>>m;
    vector<vector<int>> aux(n+1);
    for(int i = 0; i < m; ++i){
        //cin>>x>>y;
        fin>>x>>y;
        aux[x].push_back(y);
       // aux[y].push_back(x);
    }

    Graph g = Graph(n, aux);
    g.solve_ctc();
    return 0;
}