Cod sursa(job #2117762)

Utilizator CojocariuAlexandruCojocariu Alexandru CojocariuAlexandru Data 29 ianuarie 2018 16:46:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <vector>
#define NMAX 100005
#define MMAX 200005


using namespace std;

const char inname[] = "ctc.in";
const char outname[] = "ctc.out";
ifstream fin(inname);
ofstream fout(outname);

struct liste{
    vector<int> vecini;
};
liste L[NMAX];
struct listetr{
    vector<int> vecinitr;
};
struct elemente{
    vector<int> elem;
};
elemente E[NMAX];
listetr LT[NMAX];
int viz[NMAX], viztr[NMAX], noduridfs[NMAX];
int i, j, n, lg, m, lgf;

void citire();
void dfs(unsigned int);
void dfsinvers(unsigned int);

int main(){
    citire();
    for(i=1; i<=n; i++)
        if(viz[i] == 0)
            dfs(i);
    for(i=lg; i>=1; i--)
        if(viztr[noduridfs[i]] == 0){
            dfsinvers(noduridfs[i]);
            lgf++;
            }
    fout << lgf << '\n';
    for(i=0; i<lgf; i++){
        for(j=0; j<E[i].elem.size(); j++)
            fout << E[i].elem[j] << ' ';
        fout << '\n';
        }
    fin.close();
    fout.close();
    return 0;
}

void citire(){
    int i, x, y;
    fin >> n >> m;
    for(i=1; i<=m; i++){
        fin >> x >> y;
        L[x].vecini.push_back(y);
        LT[y].vecinitr.push_back(x);
        }
}

void dfs(unsigned int x){
    unsigned int i, aux;
    viz[x] = 1;
    for(i=0; i<L[x].vecini.size(); i++)
        if(viz[L[x].vecini[i]] == 0){
            aux = L[x].vecini[i];
            dfs(aux);
            }
    lg++;
    noduridfs[lg] = x;
}

void dfsinvers(unsigned int x){
    unsigned int i, aux;
    viztr[x] = 1;
    E[lgf].elem.push_back(x);
    for(i=0; i<LT[x].vecinitr.size(); i++)
        if(viztr[LT[x].vecinitr[i]] == 0){
            viztr[LT[x].vecinitr[i]] = 1;
            aux = LT[x].vecinitr[i];
            dfsinvers(aux);
            }
}