Cod sursa(job #3284102)

Utilizator Luca07Nicolae Luca Luca07 Data 11 martie 2025 09:28:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include<vector>
#include<algorithm>
using namespace std;

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

vector<vector<int>> graph;
vector<vector<int>> rgraph;

void dfs1(int u,vector<bool>& visited,vector<int>& path){
    visited[u]=true;
    for(auto v:graph[u]){
        if(!visited[v]){
            dfs1(v,visited,path);
        }
    }
    path.push_back(u);
}

void dfs2(int u,vector<bool>& visited,vector<int>& path){
    visited[u]=true;
    for(auto v:rgraph[u]){
        if(!visited[v]){
            dfs2(v,visited,path);
        }
    }
    path.push_back(u);
}

vector<vector<int>> getCTC(int n){
    vector<bool> visited=vector<bool>(n+2,false);
    vector<int> path;

    for(int i=1;i<=n;i++){
        if(!visited[i])
            dfs1(i,visited,path);
    }
    reverse(path.begin(),path.end());

    visited=vector<bool>(n+2,false);
    vector<vector<int>> ctc;

    for(auto v:path){
        if(!visited[v]){
            ctc.push_back({});
            dfs2(v,visited,*ctc.rbegin());
        }
    }
    return ctc;
}

int main()
{
    int i,j,n,m,u,v;

    cin>>n>>m;
    graph.resize(n+2);
    rgraph.resize(n+2);

    for(i=0;i<m;i++){
        cin>>u>>v;
        graph[u].push_back(v);
        rgraph[v].push_back(u);
    }

    vector<vector<int>> ctc = getCTC(n);

    cout<<ctc.size()<<"\n";
    for(auto v:ctc){
        for(auto u:v){
            cout<<u<<" ";
        }
        cout<<"\n";
    }

    return 0;
}