Cod sursa(job #3284422)

Utilizator LuciBBadea Lucian LuciB Data 11 martie 2025 17:04:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1e5;
const int MMAX = 2e5;

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

vector<int> graph[NMAX], revGraph[NMAX], stackOrder, strongComp[NMAX];
bool vis[NMAX];

void dfs(int node, vector<int>* g, vector<int>& v) {
    vis[node] = true;
    for(auto x : g[node]) {
        if(!vis[x]) {
            dfs(x, g, v);
        }
    }
    v.push_back(node);
}

int main() {
    int n, m;
    fin >> n >> m;
    for(int i = 0; i < n; i++)
        vis[i] = false;
    for(int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        revGraph[b].push_back(a);
    }
    for(int i = 0; i < n; i++) {
        if(!vis[i]) {
            dfs(i, graph, stackOrder);
        }
    }
    for(int i = 0; i < n; i++)
        vis[i] = false;
    int noComp = 0;
    while(!stackOrder.empty()) {
        int node = stackOrder.back();
        stackOrder.pop_back();
        if(!vis[node]) {
            dfs(node, revGraph, strongComp[noComp]);
            noComp++;
        }
    }
    fout << noComp << '\n';
    for(int i = 0; i < noComp; i++) {
        for(auto x : strongComp[i])
            fout << x + 1 << ' ';
        fout << '\n';
    }
    return 0;
}