Cod sursa(job #2928758)

Utilizator adeladanescuAdela Danescu adeladanescu Data 23 octombrie 2022 20:18:03
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream f("ctc.in");
ofstream c("ctc.out");
int a[100][100],n,m,nrc,suc[100],pred[100], i;

void citire()
{int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {f>>x>>y;
        a[x][y]=1;
    }
}

void dfsuc(int nod)
{int k;
    suc[nod]=nrc;
    for(k=1;k<=n;k++)
        if(a[nod][k]==1 && suc[k]==0)
            dfsuc(k);
}
void dfpred(int nod)
{int k;
    pred[nod]=nrc;
    for(k=1;k<=n;k++)
        if(a[k][nod]==1 && pred[k]==0)
            dfpred(k);
}

int main()
{citire();
    nrc=1;
    for(int i=1;i<=n;i++)
        if(suc[i]==0)
        {dfsuc(i);
            dfpred(i);
            for(int j=1;j<=n;j++)
                if(suc[j]!=pred[j])
                    suc[j]=pred[j]=0;
            nrc++;
        }
    c<<nrc-1<<endl;
    for(i=1;i<nrc;i++)
    {
        for(int j=1;j<=n;j++)
            if(suc[j]==i) c<<j<<" ";
        c<<endl;
    }
    return 0;
}