Cod sursa(job #2483630)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 29 octombrie 2019 23:12:40
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 100000
#define UNVISITED -1
using namespace std;

int dfsNumberCounter,numSCC;
int id[NMAX],low[NMAX];
bool onStack[NMAX];
vector <int> Stack;
vector <int> G[NMAX];
vector <int> components[NMAX];

void tarjanSCC(int nod){
    int to;
    id[nod] = low[nod] = dfsNumberCounter++;
    Stack.push_back(nod);
    onStack[nod] = true;
    for(int j=0;j<(int)G[nod].size();j++){
        to = G[nod][j];
        if(id[to] == UNVISITED)
            tarjanSCC(to);
        if(onStack[to] == true)
            low[nod] = min(low[nod], low[to]);
    }

    if(low[nod] == id[nod]){
        to = Stack.back();
        Stack.pop_back();
        while(to != nod){
            components[numSCC].push_back(to);
            to = Stack.back();
            Stack.pop_back();
        }
        components[numSCC].push_back(nod);
        numSCC++;
    }
}

int main()
{
    FILE *fin, *fout;
    int n,e,i,j,u,v;
    fin = fopen("ctc.in","r");
    fout = fopen("ctc.out","w");
    fscanf(fin,"%d %d",&n,&e);
    for(i=0;i<e;i++){
        fscanf(fin,"%d %d",&u,&v);
        G[u].push_back(v);
    }
    for(i=1;i<=n;i++)
        id[i] = UNVISITED;

    for(i=1;i<=n;i++)
        if(id[i] == UNVISITED)
            tarjanSCC(i);
    fprintf(fout,"%d\n",numSCC);
    for(i=0;i<numSCC;i++){
        for(j=0;j<(int)components[i].size();j++)
            fprintf(fout,"%d ",components[i][j]);
        fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}