Cod sursa(job #1118391)

Utilizator bratiefanutBratie Fanut bratiefanut Data 24 februarie 2014 10:42:29
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>

using namespace std;

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

long long int n, m, nrc = 1;
int suc[100000], pred[100000], viz[100000];
vector<long long int> graf1[100000], graf2[100000];

void citire()
{
    long long int a, b;
    f>>n>>m;
    while(f>>a>>b)
        {
            graf1[a].push_back(b);
            graf2[b].push_back(a);
        }
    f.close();
}

void df1(long long int nod)
{
    suc[nod] = nrc;
    viz[nod] = 1;
    for(long long int i = 1; i <= graf1[nod].size(); i++)
        if(viz[graf1[nod].at(i)]==0)
        df1(graf1[nod].at(i));
}
void df2(long long int nod)
{
    pred[nod] = nrc;
    viz[nod] = 1;
    for(long long int i = 1; i <= n; i++)
        if(viz[graf2[nod].at(i)]==0)
        df2(graf2[nod].at(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;
}