Cod sursa(job #2120963)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 3 februarie 2018 10:25:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int NMax = 100005;
vector < int > G[NMax];
vector < int > rez[NMax];
stack < int > st;
bitset < NMax > onStack;
int N, M, index = 1, ctc;
int viz[NMax], low[NMax];

void Tarjan(int nod)
{
    low[nod] = viz[nod] = index;
    ++index;
    st.push(nod);

    onStack[nod] = 1;

    vector < int > ::iterator it;

    for(it=G[nod].begin(); it!=G[nod].end(); ++it)
    {
        int next_nod = *it;
        if(!viz[next_nod])
        {
            Tarjan(next_nod);
            low[nod] = min(low[nod], low[next_nod]);
        }

        else if(onStack[next_nod])
        {
            low[nod] = min(low[nod], viz[next_nod]);
        }
    }

    if(low[nod] == viz[nod])
    {
        ++ctc;
        int no;
        do
        {
            no = st.top();
            rez[ctc].push_back(no);
            st.pop();
            onStack[no] = 0;
        }while(no != nod);
    }
}

void Read()
{
    fin >> N >> M;
    for(int i=1; i<=M; ++i)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }
}


int main()
{
    Read();
    for(int i=1; i<=N; ++i)
        if(!viz[i])
        {
            Tarjan(i);
        }

    fout << ctc << "\n";

    for(int i=1; i<=ctc; ++i)
    {
        vector < int > ::iterator it;

        for(it=rez[i].begin(); it!=rez[i].end(); ++it)
        {
            fout << *it << " ";
        }

        fout << "\n";
    }

    return 0;
}