Cod sursa(job #3153619)

Utilizator Alle43221Moroz Alexandra-Ioana Alle43221 Data 30 septembrie 2023 14:17:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

vector <vector<int>> G;
vector <vector<int>> GT;
vector <bool> V;
vector <vector<int>> comp;
stack <int> s;

int n, m, cate;

void dfs(int x){
    for(auto i: G[x]){
        if(!V[i]){
            V[i]=1;
            dfs(i);
        }
    }
    s.push(x);
    //cout<<x<<' ';
}

void dfsGT(int x){
    comp[cate].push_back(x);
    //cout<<x<<' ';
    for(auto i: GT[x]){
        if(!V[i]){
            V[i]=1;
            dfsGT(i);
        }
    }
}

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

    V=vector<bool> (n+1, false);
    for(int i=1; i<=n; i++){
        if(V[i]==false){
            V[i]=1;
            dfs(i);
        }
    }
    V=vector<bool> (n+1, false);
    comp = vector<vector<int>>(n+1);
    while(!s.empty()){
        x=s.top();
        if(V[x]==false){
            cate++;
            V[x]=1;
            dfsGT(x);
        }
        s.pop();
    }

    fout<<cate<<'\n';

    for(int i=1; i<=cate; i++){
        for(auto j: comp[i]){
            fout<<j<<' ';
        }
        fout<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}