Cod sursa(job #2285449)

Utilizator marcogoldPop Mihali Marco Silviu marcogold Data 18 noiembrie 2018 16:41:38
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

ofstream fo("ctc.out");
ifstream fi("ctc.in");

vector <int> graf[200005],grafT[200005];
stack <int> FinishingTimeOrd;
set <int>sol[100005];
bool vizitat[100005];
int a,b,n,m,nrElemTConex;

void DFS1(int nodCurent)
{

    vizitat[nodCurent]=true;

    for(auto vecin:graf[nodCurent])
    {
        if(vizitat[vecin]==false)
            DFS1(vecin);
    }

    FinishingTimeOrd.push(nodCurent);
}

void DFS2(int nodCurent)
{

    vizitat[nodCurent]=true;

    for(auto vecin:grafT[nodCurent])
        if(vizitat[vecin]==false)
            DFS2(vecin);

    sol[nrElemTConex].insert(nodCurent);

}

int main()
{

    fi>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fi>>a>>b;
        graf[a].push_back(b);
        grafT[b].push_back(a);

    }

    for(int i=1; i<=n; i++)
    {
        if(vizitat[i]==false)
        {

            DFS1(i);
        }
    }

    for(int i=1; i<=n; i++)vizitat[i]=false;

    while(FinishingTimeOrd.empty()==false)
    {
        int a=FinishingTimeOrd.top();
        FinishingTimeOrd.pop();

        if(vizitat[a]==false)
        {
            nrElemTConex++;
             DFS2(a);
        }

    }


    fo<<nrElemTConex<<"\n";

    for(int i=1; i<=nrElemTConex; i++)
    {

        for(int a: sol[i])
            fo<<a<<" ";
        fo<<"\n";
    }
    return 0;
}