Cod sursa(job #2199375)

Utilizator petrut22Petrut petrut22 Data 27 aprilie 2018 14:32:43
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N=105;
int n,m,a[N][N],comptc[N],ap[N],Nr;
void citire()
{
    int i,x,y;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        a[x][y]=1;
    }
}
void royfloyd()
{
    int i,j,k;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(a[i][k] && a[k][j] && i!=j && !a[i][j])
                    a[i][j]=1;
}
void smecherie()
{
    int vf,i,nr,j;
    vf=1;
    nr=1;
    comptc[vf]=nr;

    do
    {
        for(i=1; i<=n; i++)
            if(a[vf][i] && !comptc[i] && a[i][vf])
            {
                comptc[i]=nr;
            }
        vf=0;
        i=1;
        while(i<=n && vf==0)
        {
            if(!comptc[i])
            {
                vf=i;
                nr++;
                comptc[i]=nr;
            }
            i++;
        }
    }
    while(vf);
    for(i=1; i<=n; i++)
        ap[comptc[i]]++;

    for(i=1; i<=n; i++)
        if(ap[i]) Nr++;
    g<<Nr<<endl;
    for(i=1; i<=n; i++)
    {
        if(ap[i])
            for(j=1; j<=n; j++) if(comptc[j]==i) g<<j<<" ";
        g<<endl;
    }
}
int main()
{
    citire();
    royfloyd();
    smecherie();
}