Cod sursa(job #679517)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 13 februarie 2012 13:26:54
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <string>
#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;
int Plus[NMAX];
int Minus[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 afis(LIST *L)
{
    for(NOD* q=L->prim; q; q=q->next){
        g << q->inf << ' ';
    }
    g << '\n';
}

void dfs(LIST G[],int x,int a[],int p)
{
    a[x] = p;
    for (NOD *q=G[x].prim; q; q=q->next){
        if (a[q->inf]!=p){
            dfs(G,q->inf,a,p);
        }
    }
}

void compTareConexe()
{
    stringstream ss;
    string s;
    int i, j, nr=0;
    for (i=1; i<=N; i++){
        if(!b[i]){
            nr++;
            dfs(G,i,Plus,nr);
            dfs(GT,i,Minus,nr);
            for (j=1; j<=N; j++){
                if (Plus[j]==nr && Minus[j]==nr){
                    ss << j << ' ';
                    b[j] = nr;
                }
            }
            ss << '\n';
        }
    }
    g << nr << '\n';
    g << ss.str();
}

int main()
{
    int i, x, y;
    f >> N >> M;
    for (i=0; i<M; i++){
        f >> x >> y;
        insereaza(&G[x],y);
        insereaza(&GT[y],x);
    }
    //afis(&GT[3]);
    compTareConexe();
    return 0;
}