Cod sursa(job #1250482)

Utilizator ioanaandraciobanuIoana Andra Ciobanu ioanaandraciobanu Data 28 octombrie 2014 10:25:58
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#define NMAX 101
using namespace std;
ofstream fout ("ctc.out");
char uz[NMAX];
int A[NMAX][NMAX], AT[NMAX][NMAX];
char v1[NMAX], v2[NMAX];
int n, m;

void citire(); void DFS(int, char[], int A[NMAX][NMAX]); void rez();

int main()
{
    citire();
    rez();
    return 0;
}

void citire()
{
    ifstream fin ("ctc.in");
    fin>>n>>m;
    int i, x, y;
    for (i=1; i<=m; ++i)
        {
            fin>>x>>y;
            //am arc de la x la y
            A[x][++A[x][0]]=y;
            //in graful transpus, am arc de la y la x
            AT[y][++AT[y][0]]=x;
        }
    fin.close();
    return;
}

void rez()
{
    //DFS pentru graful initial
    //DFS pentru graful transpus
    int i, j;
    for (i=1; i<=n; ++i)
        if (!uz[i])
        {
            DFS (i, v1, A);
            DFS (i, v2, AT);
            //afisez componenta conexa
            for (j=1; j<=n; ++j)
            {
                if (v1[j] && v2[j])
                {
                    fout<<j<<" ";
                    uz[j]=1;//se afla intr-o componenta conexa
                }
                v1[j]=v2[j]=0;
            }
            fout<<"\n";
        }
    fout.close();
    return;
}

void DFS (int vf, char v[], int A[NMAX][NMAX])
{
    int i;
    v[vf]=1;//acest varf este accesibil

    for (i=1; i<=A[vf][0]; ++i)
        if (!v[A[vf][i]])
            DFS (A[vf][i], v, A);
    return;
}