Cod sursa(job #2216142)

Utilizator Horia14Horia Banciu Horia14 Data 25 iunie 2018 15:05:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;

vector<int>g[MAX_N+1], scc[MAX_N+1];
int visitedTime[MAX_N+1], lowTime[MAX_N+1], st[MAX_N+1], n, m, time, numSCC, vf;
bool onStack[MAX_N+1];

inline int minim(int x, int y) {
    if(x <= y) return x;
    return y;
}

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);
    }
    fclose(fin);
}

void dfsTarjan(int node) {
    visitedTime[node] = lowTime[node] = ++time;
    st[++vf] = node;
    onStack[node] = true;
    for(auto i : g[node]) {
        if(!visitedTime[i]) {
            dfsTarjan(i);
            lowTime[node] = minim(lowTime[node],lowTime[i]);
        } else if(onStack[i])
            lowTime[node] = minim(lowTime[node],lowTime[i]);
    }
    if(visitedTime[node] == lowTime[node]) {
        do {
            scc[numSCC].push_back(st[vf]);
            onStack[st[vf]] = false;
            vf--;
        }while(st[vf+1] != node);
        ++numSCC;
    }
}

void DFS_master() {
    for(int i = 1; i <= n; i++)
        if(!visitedTime[i])
            dfsTarjan(i);
}

void printSCC() {
    int i, k, j;
    FILE* fout = fopen("ctc.out","w");
    fprintf(fout,"%d\n",numSCC);
    for(i = 0; i < numSCC; i++) {
        k = scc[i].size();
        for(j = 0; j < k; j++)
            fprintf(fout,"%d ",scc[i][j]);
        fprintf(fout,"\n");
    }
    fclose(fout);
}

int main() {
    readGraph();
    DFS_master();
    printSCC();
    return 0;
}