Cod sursa(job #3240306)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 14 august 2024 00:29:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include<bits/stdc++.h>
using namespace std;

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

int n, m, x, y;
vector<vector<int> > G, GT, componente;
vector<int> comp, viz;
stack<int> order;

void dfs(int start){
    viz[start] = 1;
    for(int x : G[start])
        if(!viz[x])
            dfs(x);
    order.push(start);
}

void dfsT(int start){
    viz[start] = 1;
    comp.push_back(start);
    for(int x : GT[start])
        if(!viz[x])
            dfsT(x);
}

int main(){
    fin >> n >> m;

    G.resize(n + 1);
    GT.resize(n + 1);
    viz.resize(n + 1);

    for(;m--;){
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            dfs(i);

    viz = vector<int>(n + 1);

    for(;!order.empty(); order.pop())
    if(!viz[order.top()]){
        dfsT(order.top());
        componente.push_back(comp);
        comp.clear();
    }

    fout << componente.size() << '\n';
    for(auto c : componente){
        for(int x : c)
            fout << x << ' ';
        fout << '\n';
    }
}