Cod sursa(job #2608734)

Utilizator CristiPopaCristi Popa CristiPopa Data 1 mai 2020 18:19:03
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 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<string> get_result() {
        string component;
        vector<int> reord;
        vector<string> ctc;
        vector<bool> visited(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                dfs(i, visited, reord);
            }
        }
        reverse(reord.begin(), reord.end());
        for (int i = 0; i < n; ++i) {
            component = "";
            if (visited[reord[i]]) {
                dfsT(reord[i], visited, component);
                ctc.push_back(component);
            }
        }
        return ctc;
    }

    void dfsT(int node, vector<bool> &visited, string &component) {
        visited[node] = false;
        if (nodesT[node].empty()) {
            component += to_string(node);
            return;
        }
        component += to_string(node);
        component += " ";
        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]) {
                    cout << i << "   ";
                dfs(i, visited, reord);
            }
        }
        reord.push_back(node);
    }

    void print_output(vector<string> result) {
        ofstream fout("ctc.out");
        int q = result.size();
        fout << q << endl;
        for (int i = 0; i < q; ++i) {
            fout << result[i] << 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;
}