Cod sursa(job #2890279)

Utilizator Yato2Denis Scutariu Yato2 Data 15 aprilie 2022 09:58:18
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

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

vector <int> G[1005];
vector <int> GT[1005];
stack <int> S;
int n, m;
int f[1005];
int nr;
vector <int> result[1005];

void dfs1(int s) {
    f[s] = 1;
    for(size_t i = 0; i < G[s].size(); i++) {
        int vecin = G[s][i];
        if(f[vecin] == 0)
            dfs1(vecin);
    }
    S.push(s);
}

void dfs2(int s) {
    f[s] = 2;
    result[nr].push_back(s);
    for(size_t i = 0; i < GT[s].size(); i++) {
        int vecin = GT[s][i];
        if(f[vecin] == 1)
            dfs2(vecin);
    }
}

int main() {

    in >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y;
        in >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for(int i = 1; i <= n; i++) {
        if(!f[i])
            dfs1(i);
    }

    while(!S.empty()) {
        int nod = S.top();
        if(f[nod] == 1) {
            dfs2(nod);
            nr++;
        }

        S.pop();
    }

    out << nr << '\n';
    for(size_t i = 0; i < nr; i++, out << '\n') {
        for(size_t j = 0; j < result[i].size(); j++)
            out << result[i][j] << ' ';
    }


    return 0;
}