Cod sursa(job #2370603)

Utilizator mariastStoichitescu Maria mariast Data 6 martie 2019 12:48:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector<int> G[100100],GT[100100],sol[100100];
int viz1[100100],viz2[100200],n,m,x,y,k,nr,st[100100];
void dfs1(int x){
    viz1[x]=1;
    for(int i=0;i<G[x].size();++i){
        if(!viz1[G[x][i]]) dfs1(G[x][i]);
    }
    st[++k]=x;
}
void dfs2(int x){
    viz2[x]=nr;
    for(int i=0;i<GT[x].size();++i){
        if(!viz2[GT[x][i]]) dfs2(GT[x][i]);
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i){
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(int i=1;i<=n;++i){
        if(!viz1[i]){
            dfs1(i);
        }
    }
    while(k){
        nr++;
        dfs2(st[k]);
        while(viz2[st[k]])
            --k;
    }
    g<<nr<<'\n';
    for(int i=1;i<=n;++i){
        sol[viz2[i]].push_back(i);
    }
    for(int i=1;i<=nr;++i){
        for(int j=0;j<sol[i].size();++j){
            g<<sol[i][j]<<" ";
        }
        g<<'\n';
    }
    return 0;
}