Cod sursa(job #1610974)

Utilizator AndyCatrunaCatruna Andy AndyCatruna Data 23 februarie 2016 21:07:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <stack>
#define dim 200005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,i,j,m,is[dim],niv[dim],low[dim],c,ctc,a,b;
vector < int > v[dim],sol[dim];
stack <int> st;
void dfs(int nod){
    ++c;
    niv[nod]=c;
    low[nod]=c;
    st.push(nod);
    is[nod]=1;
    for(int i=0;i<v[nod].size();i++){
        int vecin=v[nod][i];
        if(niv[vecin]==0){
            dfs(vecin);
        }
        if(is[vecin]==1){
            low[nod]=min(low[nod],low[vecin]);
        }
    }
    if(low[nod]==niv[nod]){
        ctc++; int x=0;
        do{
            x= st.top();
            st.pop();
            is[x]=0;
            sol[ctc].push_back(x);

        }while(x!=nod);
    }
}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        v[a].push_back(b);
    }
    for(i=1;i<=n;i++){
        if(niv[i]==0){
            dfs(i);
        }
    }

    fout<<ctc<<"\n";
    for(i=1;i<=ctc;i++){
        for(j=0;j<sol[i].size();j++){
            fout<<sol[i][j]<<" ";
        }
        fout<<"\n";
    }


}