Cod sursa(job #2930615)

Utilizator GeorgeNistorNistor Gheorghe GeorgeNistor Data 28 octombrie 2022 21:52:47
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.82 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <stack>

using namespace std;

class Graph{
    list<int> *adj; // un array de liste de adiacente
    int V;          // nr. de noduri
public:
    Graph(int V=0);
    Graph& operator=(const Graph& ob);
    void addEdge(int v, int w);
    void print() const;
    friend ostream& operator<<(ostream& out, const Graph& ob);
    void printSCC();
    Graph getTranspose();
    void firstDFS(int v, bool visited[], stack<int>& Stack);
    void secondDFS(int v, bool visited[], vector<int>& SCC);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V+1];
}

Graph& Graph::operator=(const Graph& ob){
    if(this != &ob) {
        this->V = ob.V;
        this->adj = new list<int>[ob.V + 1];
        for (int i = 1; i <= V; i++)
            for (auto it: ob.adj[i])
                this->addEdge(it, i);
    }
    return *this;
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::print() const {
    for (int i = 1; i <= V; i++) {
        cout << i << ": ";
        for (auto e: adj[i])
            cout << e << " ";
        cout << endl;
    }
}
ostream& operator<<(ostream& out, const Graph& ob){
    ob.print();
    return out;
}

Graph Graph::getTranspose(){
    Graph gT(V);
    for(int e = 1; e <= V; e++)
        for(auto v: adj[e])
            gT.addEdge(e, v);
    return gT;
}

void Graph::firstDFS(int v, bool visited[], stack<int>& Stack){
    visited[v] = true;
    for(auto e: adj[v]){
        if(!visited[e])
            firstDFS(e, visited, Stack);
    }
    Stack.push(v);
}

void Graph::secondDFS(int v, bool visited[], vector<int>& SCC){
    SCC.push_back(v);
    visited[v] = true;
    for(auto e: adj[v])
        if(!visited[e])
            secondDFS(e, visited, SCC);
}

ofstream fout("ctc.out");
void Graph::printSCC() {
    vector<vector<int>> allSCC;
    stack<int> Stack;
    bool *visited = new bool[V+1];
    for(int i = 1; i <= V; i++)
        visited[i] = false;
    for(int i = 1; i <= V; i++)
        if(!visited[i])
            firstDFS(i, visited, Stack);
    //Generam graful transpus al lui g
    Graph gT;
    gT = this->getTranspose();
    for(int i = 1; i <= V; i++)
        visited[i] = false;
    while(!Stack.empty()){
        int v = Stack.top();
        Stack.pop();
        if(!visited[v]) {
            vector<int> SCC;
            gT.secondDFS(v, visited, SCC);
            allSCC.push_back(SCC);
        }
    }
    fout << allSCC.size() << endl;
    for(const auto &i: allSCC){
        for(const auto &v: i)
            fout << v << ' ';
        fout << endl;
    }
}

int main(){
    ifstream fin("ctc.in");
    int V, E;
    // Citim graful g
    fin >> V >> E;
    Graph g(V);
    for(int i = 0; i < E; i++) {
        int v, w;
        fin >> v >> w;
        g.addEdge(v, w);
    }
    g.printSCC();
    fout.close();
}