Cod sursa(job #2086356)

Utilizator andrei13Paval Andrei andrei13 Data 11 decembrie 2017 22:05:02
Problema Componente tare conexe Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <list>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack <int> s;

int n,m,T,nr,index[32000],low[32001];
list <int> lista[32001];
bool st[32001];
void sc(int v);
void tarjan()
{
    for(int i=1; i<=n; i++)
        if(!index[i])
            sc(i);
}
int k=1;
void sc(int v)
{
    index[v]=k;
    low[v]=k;
    k++;
    s.push(v);
    st[v]=true;
    list <int> :: iterator it,sf;
    sf=lista[v].end();
    it=lista[v].begin();

    while(it!=sf)
    {
        int w=*it;
        if(!index[w])
        {
            sc(w);
            low[v]=min(low[v],low[w]);
        }
        else if(st[w])
            low[v]=min(low[v],index[w]);
        ++it;
    }
    if(low[v]==index[v])
    {
        int w;
        do
        {
            w=s.top();
            s.pop();
            st[w]=false;
        }
        while(v!=w);
        nr++;
    }
}
int main()
{
    f>>n>>m;
    int i,j;
    while(m--)
    {
        f>>i>>j;
        lista[i].push_back(j);
    }
    tarjan();
    g<<nr;
    return 0;
}