Cod sursa(job #2928902)

Utilizator fredtuxFlorin Dinu fredtux Data 24 octombrie 2022 04:47:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>

using namespace std;

ostream &operator<<(ostream &out, vector<int> v) {
    for (auto x: v) {
        out << x << " ";
    }
    out << "\n";

    return out;
}

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

int n, m, i, j, tmp1, tmp2, ctc;
vector<vector<int>> graf;
vector<bool> visited;
vector<vector<int>> transpus;
stack<int> tst;
vector<vector<int>> result;
vector<int> partial;

/**
 * Sortare topologica
 * @param n
 */
inline void topSort(const int &n){
    visited[n] = true;

    for(const int &vecin : graf[n]){
        if(!visited[vecin]){
            topSort(vecin);
        }
    }

    tst.push(n);
}

/**
 * Parcurgere DFS
 * @param n
 */
void dfs(const int &n){
    visited[n] = true;

    for(const int &vecin : transpus[n]){
        if(!visited[vecin]){
            dfs(vecin);
        }
    }

    partial.push_back(n);
}

int main() {
    fin >> n >> m;

    graf.resize(n + 1);
    visited.resize(n + 1, false);
    transpus.resize(n + 1);

    // Construim graful si transpusa sa
    for(i = 0; i < m; ++i){
        fin >> tmp1 >> tmp2;
        graf[tmp1].push_back(tmp2);
        transpus[tmp2].push_back(tmp1);
    }

    // Facem sortare topologica pe graf
    for(i = 1; i <= n; ++i){
        if(!visited[i])
            topSort(i);
    }

    visited.erase(visited.begin(), visited.end());
    visited.resize(n + 1, false);

    // Trecem prin stiva sortarii topologice pana ramanem fara elemente
    while(!tst.empty()){
        tmp1 = tst.top();
        tst.pop();

        // Daca elementul nu a fost vizitat, pornim un DFS in trasnpusa
        if(!visited[tmp1]){
            ++ctc;

            partial.erase(partial.begin(), partial.end());

            dfs(tmp1);

            result.push_back(partial);
        }
    }

    fout << ctc << '\n';

    for(const vector<int> &comp : result)
        fout << comp;

    return 0;
}