Cod sursa(job #1611697)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 24 februarie 2016 12:48:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#include<vector>
#include<stack>
#define DIM 100005
using namespace std;
int n, m, x, y, nr, cnt, i, j;
vector<int> v[DIM], sol[DIM];
int niv[DIM], low[DIM], viz[DIM], f[DIM];
stack<int> s;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfs(int nod){
    viz[nod] = 1;
    cnt++;
    niv[nod] = low[nod] = cnt;
    s.push(nod);
    f[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(viz[vecin] == 0){
            dfs(vecin);
        }
        if(f[vecin] == 1){
            low[nod] = min(low[nod], low[vecin]);
        }
    }
    if(low[nod] == niv[nod]){
        nr++;
        int x;
        do{
            x = s.top();
            f[x] = 0;
            sol[nr].push_back(x);
            s.pop();
        }while(x != nod);
    }
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y;
        v[x].push_back(y);
    }
    for(i = 1; i <= n; i++){
        if(viz[i] == 0){
            dfs(i);
        }
    }
    fout<< nr <<"\n";
    for(i = 1; i <= nr; i++){
        for(j = 0; j < sol[i].size(); j++){
            fout<< sol[i][j] <<" ";
        }
        fout<<"\n";
    }
    return 0;
}