Cod sursa(job #3317457)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 23 octombrie 2025 17:41:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

void DFS_TOP(int node, vector<vector<int>> &graf, vector<bool> &visited, vector<int> &top) {
    visited[node] = true;

    for (auto v : graf[node])
        if (visited[v] == false) {
            DFS_TOP(v, graf, visited, top);
        }

    top.push_back(node);
}

void DFS_CTC(int node, vector<vector<int>> &graf, vector<bool> &visited, vector<int> &CT) {

    visited[node] = true;
    CT.push_back(node + 1);

    for (auto v : graf[node])
        if (visited[v] == false) {
            DFS_CTC(v, graf, visited, CT);
        }
}



int main() {
    int n, m;
    in >> n >> m;

    vector<vector<int>> graf(n);
    vector<vector<int>> grafT(n);

    for (int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;
        x--; y--;

        graf[x].push_back(y);
        grafT[y].push_back(x);
    }

    vector<bool> visited(n, false);
    vector<int> top;

    for (int i = 0; i < n; i++)
        if (visited[i] == false)
            DFS_TOP(i, graf, visited, top);


    visited.assign(n, false);
    vector<vector<int>> CT;

    for (int i = n - 1; i >= 0; i--)
        if (visited[top[i]] == false) {
            CT.push_back(vector<int>());
            DFS_CTC(top[i], grafT, visited, CT[CT.size() - 1]);
        }

    out << CT.size() << endl;

    for (auto v : CT) {
        for (auto i : v)
            out << i << " ";
        out << "\n";
    }
    return 0;
}