Cod sursa(job #679607)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 13 februarie 2012 15:58:57
Problema Componente tare conexe Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <sstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

typedef struct Nod {
    int inf;
    struct Nod *next;
} NOD;

typedef struct {
    NOD *prim;
} LIST;

#define NMAX 100010
LIST G[NMAX], GT[NMAX];
int N, M, nr=0;
int Plus[NMAX];
int b[NMAX];

void insereaza(LIST *L, int x)
{
    NOD* q=new(NOD);
    q->inf = x;
    q->next = L->prim;
    L->prim = q;
}

void dfs(int x)
{
    Plus[x] = nr;
    for (NOD *q=G[x].prim; q; q=q->next){
        if (Plus[q->inf]!=nr && !b[q->inf]){ // daca nodul q nu a fost parcurs si nu face parte dintr-o componenta tare conexa
            dfs(q->inf);
        }
    }
}

stringstream ss;
void dfsT(int x)
{
    //ss << x << ' ';
    b[x] = nr;
    for (NOD *q=GT[x].prim; q; q=q->next){
        if (Plus[q->inf]==nr && !b[q->inf]){
            dfsT(q->inf);
        }
    }
}

void compTareConexe()
{
    int i;
    for (i=1; i<=N; i++){
        if(!b[i]){
            nr++;
            dfs(i);
            dfsT(i);
            //ss << '\n';
        }
    }
    g << nr << '\n';
    //g << ss.str();
}

int main()
{
    int x, y;
    f >> N >> M;
    for (; M--;){
        f >> x >> y;
        insereaza(&G[x],y);
        insereaza(&GT[y],x);
    }
    compTareConexe();
    return 0;
}