Cod sursa(job #1249993)

Utilizator rares.darabanaDarabana Rares Tudor rares.darabana Data 27 octombrie 2014 18:45:31
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>
#define dmax 10000

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, c1, c2, nr=1, uz1[dmax], uz2[dmax], r[dmax], uzt[dmax];
int a[dmax][dmax], atr[dmax][dmax];
int m1[dmax], m2[dmax];
int aafis[dmax][dmax];

void dfsa(int vf);
void dfsatr(int vf);

int main()
{
    int i, j, k, x, y;
    fin>>n>>m;
    for (i=1; i<=m; i++)
        {
            fin>>x>>y;
            a[x][++a[x][0]]=y; //graful initial
            atr[y][++atr[y][0]]=x; //graful transpus
        }
    for (i=1; i<=n; i++)
        if (uzt[i]==0)
            {
                for (j=1; j<=n; j++) //curat vectorii uz1 si uz2
                    {
                        uz1[j]=0;
                        uz2[j]=0;
                    }
                m1[++c1]=i; //elementul de start i se regaseste in ambele multimi
                m2[++c2]=i;
                dfsa(i); //apelam dfs pt fiecare graf
                dfsatr(i);
                for (j=1; j<=c1; j++) //caut in cele 2 multimi
                    for (k=1; k<=c2; k++)
                        if (m1[j]==m2[k]) //daca un element este comun
                            {
                                aafis[nr][0]++;
                                aafis[nr][0]=m1[j];
                                uzt[m1[j]]=1; //vf face parte dintr-o componenta
                            }
                nr++;
            }
    fout<<nr<<'\n';
    for (i=1; i<=nr-1; i++)
        {
            for (j=1; j<=aafis[i][0]; j++)
                fout<<aafis[i][j]<<' ';
            fout<<'\n';
        }
    return 0;
}

void dfsa(int vf)
{
    int i;
    uz1[vf]=1; //marchez vf
    for (i=1; i<=a[vf][0]; i++) //vizitez fiecare vecin
        if (uz1[a[vf][i]]==0) //daca nu a mai fost vizitat
            {
                uz1[a[vf][i]]=1; //marchez
                m1[++c1]=a[vf][i]; //il adaug in multime
                dfsa(a[vf][i]);
            }
}

void dfsatr(int vf)
{
    int i;
    uz2[vf]=1; //marchez vf
    for (i=1; i<=atr[vf][0]; i++) //vizitez fiecare vecin
        if (uz2[atr[vf][i]]==0) //daca nu a mai fost vizitat
            {
                uz2[atr[vf][i]]=1; //marchez
                m2[++c2]=atr[vf][i]; //il adaug in multime
                dfsatr(atr[vf][i]);
            }
}