Cod sursa(job #1860450)

Utilizator mihailarminia1234Arminia Mihail mihailarminia1234 Data 28 ianuarie 2017 01:33:30
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

struct Nod
{
    int info;
    Nod *next;
};

Nod *lista[100001], *listaT[100001], *ctc[100001];
int n, m, x, y, k, nrCtc;
bool viz[100001], used[100001];

void Adauga_in_Lista(Nod **p,int nod)
{
    Nod *nou;
    nou=(Nod*)malloc(sizeof(Nod));
    nou->info=nod;
    nou->next=*p;
    *p=nou;
}

void DFSP(int nod)
{
    Nod *p;
    viz[nod]=true;
    for(p=lista[nod];p!=NULL;p=p->next)
        if(!viz[p->info]) DFSP(p->info);
}

void DFSM(int nod)
{
    Nod *p;
    used[nod]=true;
    Adauga_in_Lista(&ctc[nrCtc],nod);
    for(p=listaT[nod];p!=NULL;p=p->next)
        if(viz[p->info] && !used[p->info]) DFSM(p->info);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        Adauga_in_Lista(&lista[x],y);
        Adauga_in_Lista(&listaT[y],x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i]) DFSP(i);
    for(int i=1;i<=n;i++)
        if(!used[i])
        {
            nrCtc++;
            DFSM(i);
        }
    printf("%d\n",nrCtc);
    for(int i=1;i<=nrCtc;i++)
    {
        Nod *p;
        for(p=ctc[i];p!=NULL;p=p->next) printf("%d ",p->info);
        printf("\n");
    }
    return 0;
}