Cod sursa(job #2719237)

Utilizator MRobertMMartis Robert Marian MRobertM Data 9 martie 2021 18:28:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
/**Dându-se un graf orientat G = (V, E) se cere să se determine componentele sale tare conexe.**/

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define maxn 100001

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector<int> graf[maxn];
vector<int> trgraf[maxn];
vector<int> ctc[maxn];

stack <int> ordineNoduri;

int vizite[maxn];

void DFS_graf(int nod,int n)
{
    unsigned int i;
    int vecin;

    vizite[nod]=1;
    //zona 1
    for(i=0;i<graf[nod].size();i++)
    {   //zona 2
        vecin=graf[nod][i];

        if(vizite[vecin]==0)
        {
            DFS_graf(vecin,n);
        }   //zona 3
    }  //zona 4
    ordineNoduri.push(nod);
}
void DFS_trgraf(int nod,int n,int nrctc)
{
    unsigned int i;
    int vecin;

    vizite[nod]=2;

    ctc[nrctc].push_back(nod);

    //zona 1
    for(i=0;i<trgraf[nod].size();i++)
    {   //zona 2
        vecin=trgraf[nod][i];

        if(vizite[vecin]==1)
        {
            DFS_trgraf(vecin,n,nrctc);
        }   //zona 3
    }  //zona 4
}
int kosaraju(int n)
{
    int nod;
    int nrctc=0;

    for(nod=1;nod<=n;nod++)
    {
        if(vizite[nod]==0)
        {
            DFS_graf(nod,n);
        }
    }

    while(!ordineNoduri.empty())
    {
        nod=ordineNoduri.top();

        cout<<nod;

        if(vizite[nod]==1)
        {
            nrctc++;

            DFS_trgraf(nod,n,nrctc);
        }

        ordineNoduri.pop();
    }

    return nrctc;
}

int main()
{
    int n,m,x,y,i;
    int nrctc;

    unsigned int j;

    fin>>n>>m;

    for(i=0;i<m;i++)
    {
        fin>>x>>y;

        graf[x].push_back(y);
        trgraf[y].push_back(x);
    }

    nrctc=kosaraju(n);

    fout<<nrctc<<'\n';

    for(i=1;i<=nrctc;i++)
    {
        for(j=0;j<ctc[i].size();j++)
        {
            fout<<ctc[i][j]<<' ';
        }

        fout<<'\n';
    }

    return 0;
}