Cod sursa(job #2700983)

Utilizator balintfranceskaBalint Franceska balintfranceska Data 29 ianuarie 2021 15:27:23
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
using namespace std;
ifstream f("ctc.in"); ofstream g("ctc.out");
int n, m, nrc, a[101][101], frs[101], frp[101], ctc[101];
void DFS(int nod)
{   frs[nod]=1;
    for(int i=1; i<=n; ++i)
        if(!frs[i] && a[nod][i]) DFS(i);
}
void DFST(int nod)
{   frp[nod]=1;
    for(int i=1; i<=n; ++i)
        if(!frp[i] && a[i][nod]) DFST(i);
}
int main()
{   f>>n>>m;
    for(int i=1; i<=m; ++i)
    {	int x, y;
        f>>x>>y;
        a[x][y]=1;
    }
    for(int i=1; i<=n; ++i)
        if(ctc[i]==0)
        {   for(int j=1; j<=n; ++j) frs[j]=frp[j]=0;
            nrc++;
            DFS(i); DFST(i);
            for(int j=1; j<=n; ++j)
                if(frs[j]==1 && frp[j]==1) ctc[j]=nrc;
        }
    g<<nrc<<'\n';
    for(int i=1; i<=nrc; ++i)
    {   for(int j=1; j<=n; ++j)
            if(ctc[j]==i) g<<j<<' ';
        g<<'\n';
    }
    f.close(); g.close(); return 0;
}