Cod sursa(job #2314923)

Utilizator mihaialex14Dima Mihai mihaialex14 Data 9 ianuarie 2019 11:38:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define N 100005
using namespace std;

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

int n,m;

vector <int> G[N]; /// liste ad pt graful G
vector <int> GT[N]; /// lista ad pt graf transpus
vector <int> CTC[N]; ///memorarea componentelor tare conexe

stack <int> S; /// nodurile in ordinea timpilor de final

bool viz[N]; /// DFS pe gr G
bool vizt[N]; /// DFS pe gr transpus

int nc; /// nr comp tare conexe

void Read(){
    int i, x, y;
    fin>>n>>m;

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

    fin.close();
}

void DFS( int x ){
    viz[x] = 1;
    for(int i=0; i<G[x].size(); i++)
        if(!viz[G[x][i]]) DFS(G[x][i]);

    S.push(x);
}

void DFST( int x ){
    vizt[x] = 1;
    CTC[nc].push_back( x );
    for( int i = 0; i < GT[x].size(); i++ )
        if( !vizt[GT[x][i]] ) DFST( GT[x][i] );
}

void TimpiFinali(){
    int i;
    for(i=1; i<=n; i++)
        if(!viz[i]) DFS(i);
}

void ComponenteTareConexe(){
    int x;
    while(!S.empty())
    {
        x=S.top(); S.pop();
        if(!vizt[x])
        {
            nc++;
            DFST(x);
        }
    }
}

void Afisare(){
    fout<<nc<<"\n";
    for( int i = 1; i <= nc; i++ )
    {
        for( int j = 0; j < CTC[i].size(); j++ )
            fout<<CTC[i][j]<<' ';
        fout<<"\n";
    }

    fout.close();
}

int main()
{
    Read();
    TimpiFinali();
    ComponenteTareConexe();
    Afisare();
    return 0;
}