Cod sursa(job #2279485)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 9 noiembrie 2018 16:54:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
int N,M;
vector <int> ADJ[100001];
vector <int> ADJT[100001];
vector <int> CTC[100001];
int VIZ[100001];
stack <int> S;
stack <int> SS;
int rez=0;

void df(int v)
{
    vector <int> :: iterator it;
    VIZ[v]=1;
    for (it=ADJ[v].begin();it!=ADJ[v].end();it++)
    {
        int varf;
        varf=(*it);
        if (VIZ[varf]==0)
            df(varf);
    }
    S.push(v);
}

void dft(int v)
{
    vector <int> :: iterator it;
    VIZ[v]=1;
    CTC[rez].push_back(v);
    for (it=ADJT[v].begin();it!=ADJT[v].end();it++)
    {
        int varf;
        varf=(*it);
        if (VIZ[varf]==0)
            dft(varf);
    }
}

int main()
{
    fi>>N>>M;
    for (int i=1;i<=M;i++)
    {
        int a,b;
        fi>>a>>b;
        ADJ[a].push_back(b);
        ADJT[b].push_back(a);
    }
    /// se depun varfuri in stiva
    for (int i=1;i<=N;i++)
        if (VIZ[i]==0)
            df(i);
    /// se face df in graful transpus
    /// varfurile sunt considerate in ordinea data de stiva S
    for (int i=1;i<=N;i++)
        VIZ[i]=0;
    /// numarul de componente tare conexe

    SS=S;
    while (!S.empty())
    {
        int v;
        v=S.top();
        S.pop();
        if (VIZ[v]==0)
        {
            rez++;
            dft(v);
        }
    }
    fo<<rez<<'\n';
    for(int nrsol=1;nrsol<=rez;++nrsol)
    {
        for(auto nod:CTC[nrsol])fo<<nod<<" ";
        fo<<'\n';
    }
    fi.close();
    fo.close();
    return 0;
}