Cod sursa(job #2664617)

Utilizator VladAlexandruAnghelache Vlad VladAlexandru Data 28 octombrie 2020 23:17:24
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> rez;

void CTC(int nod, int low[], int disc[], stack<int> s,int onS[], vector<int> graf[])
{
    static int i=1;
    disc[nod]=i;
    low[nod]=i;
    i++;
    onS[i]=1;
    s.push(nod);

    for(int it : graf[nod])
    {
        if(disc[it] == -1)
        {
            CTC(it, low, disc,s,onS,graf);
            low[nod]=min(low[nod],low[it]);
        }
        else if(onS[it] == 1)
        {
            low[nod]=min(low[nod],disc[it]);
        }
    }

    if(low[nod] == disc[nod])
    {
        vector<int> v;
        while(s.top()!=nod)
        {
            int x=s.top();
            s.pop();
            onS[x]=0;
            v.push_back(x);

        }

        s.pop();
        onS[nod]=0;
        v.push_back(nod);

        rez.push_back(v);
    }

}


int main()
{
    int n,m;
    fin>>n>>m;
    vector<int> graf[n];
    int low[n]= {-1};
    int disc[n]= {-1};
    stack<int> s;
    int onS[n];


    while(m--)
    {
        int x,y;
        fin>>x>>y;
        graf[x].push_back(y);

    }

    for(int i=0; i<n; i++)
    {
        if(disc[i] == -1)
            CTC(i,low,disc,s,onS,graf);
    }

    fout<<rez.size()<<"\n";
    for(auto comp:rez)
    {
        for(auto nod:comp)
            fout<<nod<<" ";
        fout<<"\n";
    }
    return 0;
}