Cod sursa(job #2633573)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 7 iulie 2020 19:42:18
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <map>
using namespace std;

ifstream in ("ctc.in");
ofstream out("ctc.out");
int n, m, x, y, compAct, mom;
map <int,  vector <int> > muchii;
vector <vector <int> > componente;
map <int, int> disc, low, componentaTata;
stack <int> stk;
void Tarjan(int nod)
{
    low[nod]=disc[nod] = ++mom;
    stk.push(nod);
    for(auto & x : muchii[nod])
    {
        if(disc[x]==-1)
        {
            Tarjan(x);
            low[nod]=min(low[nod], low[x]);
        }
        else
        {
            low[nod]=min(low[nod], disc[x]);
        }
    }

    if(low[nod]==disc[nod])
    {
        componente.push_back(vector<int>());
        while(!stk.empty()&&stk.top()!=nod)
        {
            componente.back().push_back(stk.top());
            disc[stk.top()]+=2*n;
            componentaTata[stk.top()]=componente.size();
            stk.pop();
        }
        componente.back().push_back(stk.top());
        disc[stk.top()]+=2*n;
        componentaTata[stk.top()]=componente.size();
        stk.pop();
    }
}

int main()
{
    in>>n>>m;

    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        muchii[x].push_back(y);
        disc[x]=-1; disc[y]=-1;
    }
    for(int i=1; i<=n; i++)
        if(disc[i]==-1)
            mom=0, Tarjan(i);

    out<<componente.size()<<"\n";
    for(auto & vec: componente)
    {
        for(auto & x : vec)
            out<<x<<" ";
        out<<"\n";
    }

    return 0;
}