Cod sursa(job #2608766)

Utilizator CristiPopaCristi Popa CristiPopa Data 1 mai 2020 18:39:16
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100009

class Task {
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    int n;
    int m;
    vector<int> nodes[NMAX];
    vector<int> nodesT[NMAX];


    void read_input() {
        ifstream fin("ctc.in");
        fin >> n >> m;
        for (int i = 0; i < m; ++i) {
            int x, y;
            fin >> x >> y;
            nodes[x].push_back(y);
            nodesT[y].push_back(x);
        }
        fin.close();
    }

    vector<vector<int>> get_result() {
        vector<int> reord;
        vector<vector<int>> ctc;
        vector<bool> visited(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                dfs(i, visited, reord);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            vector<int> component;
            if (visited[reord[i]]) {
                dfsT(reord[i], visited, component);
                ctc.push_back(component);
            }
        }
        return ctc;
    }

    void dfsT(int node, vector<bool> &visited, vector<int> &component) {
        visited[node] = false;
        if (nodesT[node].empty()) {
            component.push_back(node);
            return;
        }
        component.push_back(node);
        for (int i : nodesT[node]) {
            if (visited[i]) {
                dfsT(i, visited, component);
            }
        }
    }

    void dfs(int node, vector<bool> &visited, vector<int> &reord) {
        visited[node] = true;
        if (nodes[node].empty()) {
            reord.push_back(node);
            return;
        }
        for (int i : nodes[node]) {
            if (!visited[i]) {
                dfs(i, visited, reord);
            }
        }
        reord.push_back(node);
    }

    void print_output(const vector<vector<int>> &ctc) {
        ofstream fout("ctc.out");
        int q = ctc.size();
        fout << q << endl;
        for (int i = 0; i < q; ++i) {
            for (int j : ctc[i])
                fout << j << ' ';
            fout << endl;
        }
        fout.close();
    }
};

// Please always keep this simple main function!
int main() {
    // Allocate a Task object on heap in order to be able to
    // declare huge static-allocated data structures inside the class.
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}