Cod sursa(job #2103733)

Utilizator edynator34Nechitoaia George-Edward edynator34 Data 10 ianuarie 2018 18:59:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <algorithm>

#define mx 100005

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");
int nrcomponente;
int val[mx],i,x,y,n,m;
list < int > v[mx],componente[mx];

int Tata=1;
stack < int > st;
bool stiva[mx];
int low[mx];

void dfs(int from){
    int nod;
    val[from]=Tata;
    low[from]=Tata;
    st.push(from);
    stiva[from]=true;
    Tata++;
    list < int > ::iterator it;
    for( it=v[from].begin() ; it!=v[from].end() ; it++){
        nod=*it;
        if(val[nod]==0) {
                dfs(nod);
                low[from]=min(low[from],low[nod]);
    }
        else if(stiva[nod]==1){
                low[from]=min(low[from],val[nod]);
        }}
        if(low[from]==val[from]){
                nrcomponente++;
                nod=st.top();
                do{
                    nod=st.top();
                    componente[nrcomponente].push_back(nod);
                    st.pop();
                    stiva[nod]=false;
                }while(nod!=from);

        }
}

int main(){
    in>>n>>m;
    for(i=1;i<=m;++i){
        in>>x>>y;
        v[x].push_back(y);
    }
    for(i=1;i<=n;++i){
        if(val[i]==0) dfs(i);
    }

    out<<nrcomponente<<'\n';
    list <int> ::iterator itt;
    for(i=nrcomponente;i>=1;i--){
        for(itt=componente[i].begin() ; itt!=componente[i].end() ; itt++){
            out<<*itt<<' ';
        }out<<'\n';
    }
    return 0;
}