Cod sursa(job #2755925)

Utilizator ViAlexVisan Alexandru ViAlex Data 28 mai 2021 19:57:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

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

const int mx=1e5+200;

vector<int> g[mx],gt[mx],q;
bool visited[mx];
int n,m;

void read(){
    in>>n>>m;
    int a,b;
    for(int i=0;i<m;i++){
        in>>a>>b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }
}

void dfs1(int node){
    visited[node]=true;

    for(int k:g[node]){
        if(!visited[k]){
            dfs1(k);
        }
    }

    q.push_back(node);
}

void dfs2(int node,vector<int>&comp){
    visited[node]=true;
    comp.push_back(node);
    for(int k:gt[node]){
        if(!visited[k]){
            dfs2(k,comp);
        }
    }
}

void solve(){
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            dfs1(i);
        }
    }
    for(int i=1;i<=n;i++)
        visited[i]=false;

    vector<vector<int>> result;
    for(auto iter=q.rbegin();iter!=q.rend();iter++){
        int node=*iter;
        if(!visited[node]){
            vector<int> comp;
            dfs2(node,comp);
            result.push_back(comp);
        }
    }
    out<<result.size()<<endl;

    for(auto&comp:result){
        for(int k:comp)
            out<<k<<" ";
        out<<'\n';
    }
}

int main(){
    read();
    solve();
    return 0;
}