Cod sursa(job #1249984)

Utilizator andreea.ciobanuCiobanu Andreea andreea.ciobanu Data 27 octombrie 2014 18:32:28
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#define NMAX 1000

using namespace std;

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

int init[NMAX][NMAX], trs[NMAX][NMAX];
int uz[NMAX], M1[NMAX], M2[NMAX];
int n, m, comp;

void citire();
void dfs(int vf, int mult[NMAX], int m[NMAX][NMAX]);
void conexe();
void afisare();

int main()
{
    int i, j;
    citire();
    for (i=1; i<=n; ++i)
        if (uz[i]==0)
            {
            comp++;
            dfs (i, M1, init);
            dfs (i, M2, trs);
            conexe();
            }
    afisare();
    return 0;
}
void citire()
{
    int x,y,i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
        fin>>x>>y;
        init[x][++init[x][0]]=y;
        trs[y][++trs[y][0]]=x;
        }
}
void dfs (int vf, int mult[], int m[NMAX][NMAX])
{
    int i;
    mult[vf]=1;
    for (i=1; i<=m[vf][0]; ++i)
        if (mult[m[vf][i]]==0)
            dfs (m[vf][i], mult, m);
    return;
}
void conexe()
{
    int i;
    for (i=1; i<=n; i++)
        if (M1[i]==M2[i])
            uz[i]=comp;
    for (i=1; i<=n; i++)
        M1[i]=M2[i]=0;
}
void afisare()
{
    int i, j;
    fout<<comp<<'\n';
    for (i=1; i<=comp; i++)
        {
        for(j=1; j<=n; j++)
            if (uz[j]==i)
                fout<<j<<' ';
        fout<<'\n';
        }
}