Cod sursa(job #1340366)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 11 februarie 2015 19:40:30
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#define DIM 100011
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,ctc;
int low[DIM],niv[DIM];

vector<int> L[DIM],sol[DIM];
stack<int> S;
bitset<DIM> viz,IS;

void dfs(int nod,int k){
    vector<int>::iterator it;
    int x;
    low[nod]=niv[nod]=k;
    S.push(nod);
    viz[nod]=IS[nod]=1;
    for(it=L[nod].begin();it!=L[nod].end();it++){
        if(!viz[*it]){
            dfs(*it,k+1);
            low[nod]=min(low[nod],low[*it]);
        }
        else if(IS[nod])
            low[nod]=min(low[nod],low[*it]);
    }

    if(low[nod]==niv[nod]){
        //componenta conexa
        ctc++;
        do{x=S.top(),S.pop();
            IS[x]=0;
            sol[ctc].push_back(x);
        }while(x!=nod);
    }
}

int main(void){
    register int x,y,i,j;
    vector<int>::iterator it;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        L[x].push_back(y);
    }

    for(i=1;i<=n;i++){
        if(!viz[i])
            dfs(i,1);
    }

    g<<ctc<<"\n";
    for(i=1;i<=ctc;i++){
        for(it=sol[i].begin();it!=sol[i].end();it++)
            g<<*it<<" ";
        g<<"\n";
    }
    f.close();
    g.close();
    return 0;
}