Cod sursa(job #2112124)

Utilizator Horia14Horia Banciu Horia14 Data 23 ianuarie 2018 01:02:44
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;

vector<int>G[MAX_N + 1], scc[MAX_N + 1];
int d[MAX_N + 1], st[MAX_N + 1], n, m, numScc, vf;
bool onStack[MAX_N + 1];

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

int DFS(int node, int depth) {
    d[node] = depth;
    st[++vf] = node;
    onStack[node] = true;

    for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {
        if(!d[*it]) {
            d[node] = min(d[node],DFS(*it, depth + 1));
        } else if(onStack[*it]) {
            d[node] = min(d[node], d[*it]);
        }
    }

    if(d[node] == depth) {
        while(st[vf] != node) {
            scc[numScc].push_back(st[vf]);
            onStack[st[vf]] = false;
            vf--;
        }
        scc[numScc++].push_back(st[vf]);
        onStack[st[vf]] = false;
        vf--;
    }
    return d[node];
}

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

void printSCC() {
    FILE *fout = fopen("ctc.out","w");
    fprintf(fout,"%d\n",numScc);
    for(int i = 0; i < numScc; i++) {
        for(vector<int>::iterator it = scc[i].begin(); it != scc[i].end(); it++)
            fprintf(fout,"%d ",*it);
        fprintf(fout,"\n");
    }
    fclose(fout);
}

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