Cod sursa(job #3248869)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 13 octombrie 2024 15:50:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

vector<int> v[100001],invv[100001],comp[100001];
vector<int> ordine;
int viz[100001],n;

void dfs1(int nod){
    int i;
    viz[nod]=1;
    for(i=0;i<v[nod].size();i++){
        if(viz[v[nod][i]]) continue;
        dfs1(v[nod][i]);
    }
    ordine.push_back(nod);
}

void dfs2(int nod,int comp_curenta){
    int i;
    viz[nod]=1;
    for(i=0;i<invv[nod].size();i++){
        if(viz[invv[nod][i]]) continue;
        dfs2(invv[nod][i],comp_curenta);
    }
    comp[comp_curenta].push_back(nod);
}
void reset(){
    int i;
    for(i=0;i<=n;i++) viz[i]=0;
}

int main()
{
    int m,i,j,a,b,cnt=0;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>a>>b;
        v[a].push_back(b);
        invv[b].push_back(a);
    }
    for(i=1;i<=n;i++){
        if(!viz[i]) dfs1(i);
    }
    reverse(ordine.begin(),ordine.end());
    reset();
    for(i=0;i<n;i++){
        if(viz[ordine[i]]==0){
            cnt++;
            dfs2(ordine[i],cnt);
        }
    }
    cout<<cnt<<"\n";
    for(i=1;i<=cnt;i++){
        for(j=0;j<comp[i].size();j++) cout<<comp[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}