Cod sursa(job #2175647)

Utilizator alin01alin catavencu alin01 Data 16 martie 2018 18:16:30
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
int cc[160][700],i,j,n,m,ok,viz[100005],x,y,nrcc,h,nrs[160];
bool b[4000][4000];
vector <int> a[100005];
void dfs(int j)
{
    int h,k;
    h=a[j].size();
    if(i!=j)
        b[i][j]=1;
    for(k=0;k<h;k++)
    {
        if(viz[a[j][k]]!=i)
        {
            viz[a[j][k]]=i;
            dfs(a[j][k]);
        }
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x].pb(y);
    }

    for(i=1;i<=n;i++)
    {
        viz[i]=i;
        dfs(i);
    }
    for(i=1;i<=n;i++)
    {
        ok=1;
        for(j=1;j<=nrcc&&ok;j++)
        {
            h=cc[j][1];
            if(b[i][h]&&b[h][i])
            {
                ok=0;
                nrs[j]++;
                cc[j][nrs[j]]=i;
            }
        }
        if(ok)
        {
            nrcc++;
            nrs[nrcc]=1;
            cc[nrcc][1]=i;
        }
    }
    printf("%d\n",nrcc);

    for(i=1;i<=nrcc;i++)
    {
        for(j=1;j<=nrs[i];j++)
            printf("%d ",cc[i][j]);
        printf("\n");
    }


    return 0;
}