Cod sursa(job #2472853)

Utilizator mihaela.macarie01@yahoo.comMihaela Macarie [email protected] Data 13 octombrie 2019 01:01:58
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream x("ctc.in");
ofstream y("ctc.out");

int i,j,n,m,k,viz[100002],p[100002],nr,nrc,vizi[100002],t[2][100002],start[100002],tb[2][100002],startb[100002],l;

void citire()
{
    k=0;
    for(l=1;l<=m;l++)
    {
        x>>i>>j;
        k++;
        t[0][k]=j;
        t[1][k]=start[i];
        start[i]=k;
        tb[0][k]=i;
        tb[1][k]=startb[j];
        startb[j]=k;
    }
}

void dfsb(int nod)
{
    int k;
    k=startb[nod];
    vizi[nod]=nrc;
    viz[nod]=0;
    while(k)
    {
        if(viz[tb[0][k]]==1)
            dfsb(tb[0][k]);
        k=tb[1][k];
    }
}
void dfsa(int nod)
{
    int k;
    k=start[nod];
    viz[nod]=1;
    while(k)
    {
        if(viz[t[0][k]]==0)
            dfsa(t[0][k]);
        k=t[1][k];
    }
    p[++nr]=nod;
}


int main()
{
    x>>n>>m;
    citire();
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfsa(i);
    for(i=n;i>0;i--)
        if(viz[p[i]])
        {
            nrc++;
            dfsb(p[i]);
            ///cout<<'\n';
        }
    y<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        for(j=1;j<=n;j++)
            if(vizi[j]==i)
                y<<j<<" ";
        y<<'\n';
    }
    x.close();
    y.close();
    return 0;
}