Cod sursa(job #3269114)

Utilizator ONLYGODYBochis Andrei ONLYGODY Data 18 ianuarie 2025 11:10:07
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <bits/stdc++.h>
using namespace std;

#define nl '\n'

fstream fi ("ctc.in", ios::in);
fstream fo ("ctc.out", ios::out);

vector<bool> visited;
vector<forward_list<int>> branches, tbranches;
stack<int> nodes;
int n, m;
int nrOfComponents;
list<list<int>> components;

void read();

void dfs(int, vector<bool> &, vector<forward_list<int>> &, stack<int> &);
void ccc(vector<bool> &, vector<forward_list<int>> &, stack<int> &, list<list<int>> &);
void dfst(int, vector<bool> &, vector<forward_list<int>> &, list<list<int>> &);
void print();

int main() {

    read();
    dfs(1, visited, branches, nodes);
    ccc(visited, tbranches, nodes, components);
    print();
    return 0;
}

void read() {
    int n1, n2;
    fi >> n >> m;

    visited.resize(n + 1);
    branches.resize(m + 1);
    tbranches.resize(m + 1);

    for (int i = 0; i < m; ++i) {
        fi >> n2 >> n1;
        branches[n2].push_front(n1);
        tbranches[n1].push_front(n2);
    }
}

void dfs(int node, vector<bool> &visited, vector<forward_list<int> > &branches, stack<int> &nodes) {
    visited[node] = true;

    for (auto i: branches[node]) {
        if (!visited[i]) {
            dfs(i, visited, branches, nodes);
        }
    }

    nodes.push(node);
}

void dfst(int node, vector<bool> &visited, vector<forward_list<int> > &branches, list<list<int>> &components) {
    visited[node] = true;
    components.back().push_back(node);

    for (auto i: branches[node]) {

        if (!visited[i]) {

            dfst(i, visited, branches, components);
        }
    }
}

void ccc(vector<bool> &visited, vector<forward_list<int>> &tbranches, stack<int> &nodes, list<list<int>> &components) {

    visited.assign(n + 1, false);
    while (!nodes.empty()) {

        if(!visited[nodes.top()]) {

            ++nrOfComponents;
            components.push_back({});
            dfst(nodes.top(), visited, tbranches, components);
        }

        nodes.pop();
    }
}

void print() {

    fo << nrOfComponents << nl;
    for (auto& j : components) {

        for (auto& i: j) {

            fo << i << ' ';
        }
        fo << nl;
    }
}