Cod sursa(job #2306937)

Utilizator PetruiopAldea Petru Daniel Petruiop Data 23 decembrie 2018 12:20:00
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,a[10001][10001],viz1[10001],viz2[10001],ctc[10001],nrc;
void dfs1(int x)
{
    viz1[x]=1;
    for(int i=1; i<=n; i++)
        if(a[x][i] and !viz1[i])
            dfs1(i);
}
void dfs2(int x)
{
    viz2[x]=1;
    for(int i=1; i<=n; i++)
        if(a[i][x] and !viz2[i])
            dfs2(i);
}
int main()
{
    f>>n>>m;
    int i,j;
    while(m)
    {
        f>>i>>j;
        a[i][j]=1;
        m--;
    }

    for(i=1; i<=n; i++)
    {
        if(!ctc[i])
        {
            for(j=1; j<=n; j++)
                viz1[j]=viz2[j]=0;
            nrc++;
            dfs1(i);
            dfs2(i);
            for(j=1; j<=n; j++)
                if(viz1[j]==1 && viz2[j]==1)
                    ctc[j]=nrc;
        }
    }
   g<<nrc<<'\n';
    for(i=1; i<=nrc; i++)
    {
        for(j=1; j<=n; j++)
            if(ctc[j]==i)
                g<<j<<" ";
        g<<'\n';
    }
    return 0;
}