Cod sursa(job #1114461)

Utilizator bratiefanutBratie Fanut bratiefanut Data 21 februarie 2014 17:29:26
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

long long int n, m, A[10000][10000], suc[10000], pred[10000], nrc = 1;

void citire()
{
    int a, b;
    f>>n>>m;
    while(f>>a>>b)
        A[a][b] = 1;
    f.close();
}

void df1(long long int nod)
{
    suc[nod] = nrc;
    for(long long int i = 1; i <= n; i++)
        if(A[nod][i]==1 && suc[i]==0)
        df1(i);
}
void df2(long long int nod)
{
    pred[nod] = nrc;
    for(long long int i = 1; i <= n; i++)
        if(A[i][nod] == 1 && pred[i] == 0)
        df2(i);
}

int main()
{
    citire();
    for(long long int i = 1; i <= n; i++)
    {
        if(suc[i] == 0)
        {
            suc[i]=nrc;
            df1(i); df2(i);
            for(long long int j = 1; j<=n; j++)
                if(suc[j]!=pred[j])
                suc[j]=pred[j]=0;
            nrc++;
        }
    }
    g<<nrc-1<<endl;
    for(long long int i = 1; i<nrc; i++)
    {
        for(long long int j = 1; j<=n; j++)
            if(suc[j]==i)
            g<<j<<' ';
        g<<endl;
    }
    g.close();
    return 0;
}