Cod sursa(job #2371427)

Utilizator Horia14Horia Banciu Horia14 Data 6 martie 2019 17:34:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;

vector<int>g[MAX_N+1], gt[MAX_N+1], ctc[MAX_N+1];
int f[MAX_N+1], n, m, k, nrctc;
bool used[MAX_N+1];

void readGraph() {
    int i, x, y;
    FILE* fin = fopen("ctc.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(i = 0; i < m; i++) {
        fscanf(fin,"%d%d",&x,&y);
        g[x].push_back(y);
        gt[y].push_back(x);
        //printf("%d %d\n",x,y);
    }
    fclose(fin);
}

void DFS(int nod) {
    used[nod] = true;
    for(auto i : g[nod])
        if(!used[i])
            DFS(i);
    f[k++] = nod;
}

void DFS_Master(int n) {
    for(int i = 1; i <= n; i++)
        if(!used[i])
            DFS(i);
}

void DFSreverseGraph(int nod) {
    used[nod] = true;
    ctc[nrctc].push_back(nod);
    for(auto i : gt[nod])
        if(!used[i])
            DFSreverseGraph(i);
}

void Kosaraju() {
    int i;
    DFS_Master(n);
    nrctc = 0;
    for(i = 1; i <= n; i++)
        used[i] = false;
    for(i = k - 1; i >= 0; i--)
        if(!used[f[i]]) {
            DFSreverseGraph(f[i]);
            nrctc++;
    }
}

void printCTC() {
    int j;
    FILE* fout = fopen("ctc.out","w");
    fprintf(fout,"%d\n",nrctc);
    for(j = 0; j < nrctc; j++) {
        for(auto i : ctc[j])
            fprintf(fout,"%d ",i);
        fprintf(fout,"\n");
    }
    fclose(fout);
}

int main() {
    readGraph();
    Kosaraju();
    printCTC();
    return 0;
}