Cod sursa(job #1860370)

Utilizator mihailarminia1234Arminia Mihail mihailarminia1234 Data 27 ianuarie 2017 23:39:55
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

//ifstream f("date.in");
//ofstream g("date.out");

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

Nod *lista[100001], *listaT[100001];
unsigned int n, m, x, y, comp[100001], k, mat[10001][10001], nrLinii;
bool viz[100001], vizT[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 DFS(int nod)
{
    Nod *p;
    viz[nod]=true;
    for(p=lista[nod];p!=NULL;p=p->next)
        if(!viz[p->info]) DFS(p->info);
}

void DFST(int nod)
{
    Nod *p;
    vizT[nod]=true;
    for(p=listaT[nod];p!=NULL;p=p->next)
        if(!vizT[p->info]) DFST(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(!used[i])
        {
            for(int i=1;i<=n;i++) viz[i]=vizT[i]=false;
            nrLinii++;
            DFS(i);
            DFST(i);
            k=0;
            for(int i=1;i<=n;i++)
            {
                if(viz[i] && vizT[i])
                {
                    k++;
                    mat[nrLinii][k]=i;
                    used[i]=true;
                }
            }
            mat[nrLinii][0]=k;
        }
    }
    printf("%d\n",nrLinii);
    for(int i=1;i<=nrLinii;i++)
    {
        for(int j=1;j<=mat[i][0];j++) printf("%d ",mat[i][j]);
        printf("\n");
    }
    return 0;
}