Cod sursa(job #2120957)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 3 februarie 2018 10:19:07
Problema Componente tare conexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 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];
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();
            st.pop();
        }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;

    return 0;
}