Cod sursa(job #3205375)

Utilizator AlfexAlex Florea Alfex Data 19 februarie 2024 14:18:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <vector>
#include <fstream>

#define NMAX 101

using namespace std;

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

vector<vector<int> > G, GT;

int n, m, nrTC;

vector<bool> V;
vector<int> S;
vector<vector<int>> comp;

void read(){

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

}

void dfs(int k){
    V[k] = true;
    for(auto x : G[k])
        if(!V[x])
         dfs(x);
    S.push_back(k);
}

void dfsGT(int k){
    V[k] = true;
    comp[nrTC].push_back(k);
    for(auto vecin : GT[k])
        if(!V[vecin])
            dfsGT(vecin);
}

int main()
{
    read();

    V = vector<bool> (n + 1, false);

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

    V = vector<bool> (n + 1, false);
    nrTC = 0;
    comp.push_back({});
    for(vector<int>::reverse_iterator it = S.rbegin() ; it != S.rend(); it ++)
        if(!V[*it]){
            nrTC ++;
            comp.push_back({});
            dfsGT(*it);
        }

    g << nrTC << '\n';
    for(int i = 1; i <= nrTC; i ++, g << '\n')
        for(auto x : comp[i])
           g << x << " ";

    return 0;
}