Cod sursa(job #3369426)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 20 octombrie 2026 11:30:48
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#define MAXN 100004

using namespace std;

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

void stackedDfs(vector<vector<int>>& graph, bitset<MAXN>& visited, int current, int stack[], int& index) {
    visited[current] = true;
    for (auto& neighbour : graph[current])
        if (!visited[neighbour])
            stackedDfs(graph, visited, neighbour, stack, index); 
    stack[index++] = current;
}

void dfs(vector<vector<int>>& graph, bitset<MAXN>& visited, int current, vector<int>& trace) {
    visited[current] = true;
    trace.push_back(current);
    for (auto& neighbour : graph[current])
        if (!visited[neighbour])
            dfs(graph, visited, neighbour, trace);
}

int main() {
    int n, m;
    fin >> n >> m;
    vector<vector<int>> graph(n, vector<int>());
    vector<vector<int>> grapht(n, vector<int>());
    for (int i = 1; i <= m; i++) {
        int from, to;
        fin >> from >> to;
        graph[from].push_back(to);
        grapht[to].push_back(from);
    }

    int stack[MAXN], index = 0;
    bitset<MAXN> visited; 
    for (int i = 1; i <= n; i++)
        if (!visited[i])
            stackedDfs(graph, visited, i, stack, index);

    bitset<MAXN> visitedt;
    vector<vector<int>> solution;
    while (index > 0) {
        int current = stack[--index];
        if (!visitedt[current]) {
            vector<int> trace;
            dfs(grapht, visitedt, current, trace);
            solution.push_back(trace);
        }
    }

    fout << solution.size() << '\n';
    for (auto& trace : solution) {
        for (auto& node : trace)
            fout << node << ' ';
        fout << '\n';
    }
    return 0;
}