Cod sursa(job #3272450)

Utilizator sstanciu44Stanciu Sebastian sstanciu44 Data 29 ianuarie 2025 13:46:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;

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

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& c) {
    visited[node] = true;
    for(auto& to: adj[node])
        if(!visited[to])
            dfs(to, adj, visited, c);
    c.push_back(node);
}

int main() {
    int n, m, i, x, y;
    f >> n >> m;
    vector<vector<int>> edges(n + 1), adj(n + 1), components;
    vector<int> order;
    vector<bool> visited(n + 1, false);
    for(i = 0; i < m; ++i) {
        f >> x >> y;
        edges[x].push_back(y);
        adj[y].push_back(x);
    }

    for(i = 1; i <= n; ++i)
        if(!visited[i])
            dfs(i, edges, visited, order);

    visited.assign(n, false);
    reverse(order.begin(), order.end());

    for(auto& node: order)
        if(!visited[node]) {
            vector<int> component;
            dfs(node, adj, visited, component);
            components.push_back(component);
        }


    g << components.size() << '\n';
    for(auto& c: components) {
        for(auto& node: c) {
            g << node << ' ';
        }
        g << '\n';
    }
    return 0;
}