Dddarius95
Darius-Florentin Neatu
• Dddarius95
logout | contul meu
infoarena informatica de performanta
infoarena
blog
forum
calendar
profilul meu
mesaje
Home
Arhiva de probleme
Arhiva educatională
Arhiva monthly
Arhiva ACM
Concursuri
Concursuri virtuale
Clasament
Articole
Downloads
Links
Documentaţie
Despre infoarena
Monitorul de evaluare
Trimite soluţii
Contul meu
! Cautare

In curand...
139341 membri inregistrati

12:27:41
Fii un bun infoarenaut! Implică-te!

Pagini recente » Monitorul de evaluare | Autentificare | Monitorul de evaluare | Borderou de evaluare (job #2742471) | Cod sursa (job #2742471)

Cod sursa(job #2742471)
Utilizator	Dddarius95Darius-Florentin Neatu Dddarius95	Data	21 aprilie 2021 00:01:16
Problema	Componente tare conexe	Scor	100
Compilator	cpp-64	Status	done
Runda	Arhiva educationala	Marime	5.3 kb
Raporteaza aceasta sursa
#include <bits/stdc++.h>
using namespace std;

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

private:
    // numarul maxim de noduri
    static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005

    // n = numar de noduri, m = numar de muchii/arce
    int n, m;

    // adj[node] = lista de adiacenta a nodului node
    // exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
    vector<int> adj[NMAX];

    // parent[node] = parent of node in the DFS traversal
    vector<int> parent;

    // found[node] = the timestamp when we found node (we started to visit its subtree)
    // Note: The global timestamp is incremented everytime we find a node.
    vector<int> found;

    // low_link[node] = min { found[x] | x can be accesed from node }
    //                = the minimum timestamp that node can see (directly or indirectly through its descendents)
    vector<int> low_link;

    // nodes are pushed into the stack in the order of visiting
    stack<int> nodes_stack;
    vector<bool> in_stack;

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

    vector<vector<int>> get_result() {
        // TODO: Gasiti componentele tare conexe ale grafului orientat cu n noduri, stocat in adj.
        // Rezultatul se va returna sub forma unui vector, ale carui elemente sunt componentele tare conexe detectate.
        // Nodurile si componentele tare conexe pot fi puse in orice ordine in vector.
        //

        return tarjan_scc();
    }

    vector<vector<int>> tarjan_scc() {
        // STEP 0: initialize results
        parent = vector<int>(n + 1, -1);
        found = vector<int>(n + 1, -1);
        low_link = vector<int>(n + 1, -1);
        in_stack = vector<bool>(n + 1, false);

        // STEP 2: visit all nodes for computing all SCCs
        vector<vector<int>> all_sccs;
        int timestamp = 0;                                         // global timestamp
        for (int node = 1; node <= n; ++node) {
            if (parent[node] == -1) {                              // node not visited
                parent[node] = node;                               // convention: the parent of the root is actually the root
                cout << node << '\n';
                dfs(node, timestamp, all_sccs);                    // start a new DFS traversal for substree with root in node
            }
        }

        return all_sccs;
    }

    void dfs(int node, int &timestamp, vector<vector<int>>& all_sccs) {
        // STEP 1: a new node is visited - increment the timestamp
        found[node]    = ++timestamp;                              // the timestamp when node was found
        low_link[node] = found[node];                              // node only knows its timestamp
        nodes_stack.push(node);
        in_stack[node] = true;

        // STEP 2: visit each neighbour
        int children = 0;                                          // the number of found children
        for (auto neigh : adj[node]) {
            // STEP 3: check if neigh is already visited
            if (parent[neigh] != -1) {
                // STEP 3.1: neigh already visited - update low_link[node] with information gained through neigh
                if (/*neigh != parent[node] && */in_stack[neigh]) {                       //
                    low_link[node] = min(low_link[node], found[neigh]);
                }
                continue;
            }

            // STEP 4: save parent and could children
            parent[neigh] = node;
            ++children;

            // STEP 5: recursively visit the child subree
            dfs(neigh, timestamp, all_sccs);

            // STEP 6: update low_link[node] with information gained through neigh
            low_link[node] = min(low_link[node], low_link[neigh]);
        }

        // STEP 8: check for SCCs: node is root in a SCC if low_link[node] == found[node]
        if (low_link[node] == found[node]) {
            // STEP 8.1: extract current SCC - pop nodes from stack until node is found
            vector<int> scc;
            do {
                auto x = nodes_stack.top();
                nodes_stack.pop();
                in_stack[x] = false;

                scc.push_back(x);
            } while(scc.back() != node);

            // STEP 8.2: save SCC
            all_sccs.push_back(scc);
        }
    }

    void print_output(const vector<vector<int>>& result) {
        ofstream fout("ctc.out");
        fout << result.size() << '\n';
        for (const auto& ctc : result) {
            for (auto node : ctc) {
                fout << node << ' ';
            }
            fout << '\n';
        }
        fout.close();
    }
};

// [ATENTIE] NU modifica functia main!
int main() {
    // * se aloca un obiect Task pe heap
    // (se presupune ca e prea mare pentru a fi alocat pe stiva)
    // * se apeleaza metoda solve()
    // (citire, rezolvare, printare)
    // * se distruge obiectul si se elibereaza memoria
    auto* task = new (nothrow) Task(); // hint: cppreference/nothrow
    if (!task) {
        cerr << "new failed: WTF are you doing? Throw your PC!\n";
        return -1;
    }
    task->solve();
    delete task;
    return 0;
}