Cod sursa(job #2331061)

Utilizator Valentin0709Datcu George Valentin Valentin0709 Data 29 ianuarie 2019 09:47:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define NMAX 100005

FILE * f = fopen("ctc.in", "r");
FILE * g = fopen("ctc.out", "w");

int n, m, index, ssize, nrcct, s[NMAX], idx[NMAX], lowlink[NMAX], onstack[NMAX], cct[NMAX];

struct nod{
    int inf;
    nod* urm;
} *l[NMAX];

void adaug_nod(int x, int y) {
    nod* p = new nod;

    p->inf = y;
    p->urm = l[x];
    l[x] = p;
}

void citire() {
    int x, y;

    fscanf(f, "%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        fscanf(f, "%d%d", &x, &y);
        adaug_nod(x, y);
    }
}

void tarjan1(int v) {
    int x;

    s[++ssize] = v; onstack[v] = 1;
    idx[v] = lowlink[v] = ++index;

    for(nod* p = l[v]; p != NULL; p = p->urm) {
        int u = p->inf;
        if(!idx[u]) {
            tarjan1(u);
            lowlink[v] = min(lowlink[v], lowlink[u]);
        }
        else if(onstack[u]) lowlink[v] = min(lowlink[v], idx[u]);
    }

    if(idx[v] == lowlink[v]) {
        nrcct++;
        do {
            x = s[ssize];
            cct[x] = nrcct; onstack[x] = 0;
            ssize--;
        } while(x != v);
    }
}

void tarjan2(int v) {
    int x;

    s[++ssize] = v; onstack[v] = 1;
    idx[v] = lowlink[v] = ++index;

    for(nod* p = l[v]; p != NULL; p = p->urm) {
        int u = p->inf;
        if(!idx[u]) {
            tarjan2(u);
            lowlink[v] = min(lowlink[v], lowlink[u]);
        }
        else if(onstack[u]) lowlink[v] = min(lowlink[v], idx[u]);
    }

    if(idx[v] == lowlink[v]) {
        do {
            x = s[ssize];
            fprintf(g, "%d ", x);
            onstack[x] = 0;
            ssize--;
        } while(x != v);
        fprintf(g, "\n");
    }
}

/*void afisare() {
    fprintf(g, "%d\n", nrcct);
    for(int i = 1; i <= nrcct; i++) {
        for(int j = 1; j <= n; j++)
            if(cct[j] == i) fprintf(g,"%d ", j);
        fprintf(g,"\n");
    }
}*/

int main() {

    citire();

    for(int i = 1; i <= n; i++)
        if(!idx[i]) tarjan1(i);

    fprintf(g, "%d\n", nrcct);
    for(int i = 1; i <= n; i++) idx[i] = 0;
    for(int i = 1; i <= n; i++)
        if(!idx[i]) tarjan2(i);


    fclose(f); fclose(g);

    return 0;
}