Cod sursa(job #2928466)

Utilizator DirtuEcaterinaDirtu Ecaterina DirtuEcaterina Data 22 octombrie 2022 22:58:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> *laG, *laGt, *rez;
stack <int> S;

void DFSG(int s, int viz[])
{
    viz[s]=1;
    for (int i=0; i<laG[s].size(); i++)
    {
        int y=laG[s][i];
        if(viz[y]==0)
            DFSG(y, viz);
    }
    S.push(s);
}

void DFSGt(int s, int viz[], int cnt)
{
    viz[s]=1;
    rez[cnt].push_back(s);
    for (int i=0; i<laGt[s].size(); i++)
    {
        int y=laGt[s][i];
        if(viz[y]==0)
            DFSGt(y, viz, cnt);
    }
}

int main()
{
    int n, m, x, y, cnt=0;
    fin>>n>>m;

    laG= new vector<int> [n+1];
    laGt= new vector<int> [n+1];
    rez= new vector<int> [n+1];

    int c=m;
    while (c>0)
    {
        fin>>x>>y;
        laG[x].push_back(y);
        laGt[y].push_back(x);
        c--;
    }
    /*
        for(x=0; x<n; x++)
        {
            cout<<x<<": ";
            for (int i=0; i<la[x].size(); i++)
                cout<<la[x][i]<<" ";
            cout<<endl;
        }
    */
    int viz1[n+1]= {};

    for (int i=0; i<n; i++)
        if(viz1[i]==0)
            DFSG(i, viz1);

    int viz2[n+1]= {};

    while(!S.empty())
    {
        int q=S.top();
        S.pop();
        if(viz2[q]==0)
        {
            DFSGt(q, viz2, cnt);
            cnt++;
        }
    }
    cnt--;
    fout<<cnt<<endl;
    for (int i=0; i<cnt; i++)
    {
        for (int j=0; j<rez[i].size(); j++)
            fout<<rez[i][j]<<" ";
        fout<<endl;
    }
    return 0;
}