Cod sursa(job #2556233)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 24 februarie 2020 19:28:43
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#define NMAX 100005
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int index = 1;
int n, m, nrc;
int isInStack[NMAX], viz[NMAX], lowlink[NMAX], idx[NMAX];
vector<int> graph[NMAX];
vector<int> CC[NMAX];
stack<int> S;

void read()
{
    int x, y;

    f>>n>>m;
    for(int i = 0; i < m; ++i)
    {
        f>>x>>y;
        graph[x].push_back(y);
    }
}


void addCC()
{
    nrc++;
    int top = S.top();
    do{
        CC[nrc].push_back(top);
        S.pop();
        isInStack[top] = 0;
        top = S.top();
    }while(lowlink[top] != idx[top]);

    CC[nrc].push_back(top);
    S.pop();
    isInStack[top] = 0;
}




void solve(int nod)
{
    S.push(nod);
    isInStack[nod] = 1;
    viz[nod] = 1;
    idx[nod] = index;
    lowlink[nod] = index;
    index ++;

    for(auto &v:graph[nod])
    {
        if(viz[v] == 0)
        {
            solve(v);
            lowlink[nod] = min(lowlink[nod], lowlink[v]);
        }
        else{
            if(isInStack[v] == 1)
                lowlink[nod] = min(lowlink[nod], lowlink[v]);
        }
    }

    if(lowlink[nod] == idx[nod])
    {
        addCC();
    }

}




void tarjan()
{
//    init();

    for(int i = 1; i <= n; ++i)
        if(viz[i] == 0)
            solve(i);
}


void write()
{
    g<<nrc<<"\n";
    for(int i = 1; i <= nrc; ++i)
    {
        for(auto &v:CC[i])
            g<<v<<" ";
        g<<'\n';
    }
}




int main()
{
    read();
    tarjan();
    write();
    return 0;
}