Cod sursa(job #1726735)

Utilizator vancea.catalincatalin vancea.catalin Data 8 iulie 2016 20:02:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
//tarjan
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define DX 100100
using namespace std;
fstream fin("ctc.in",ios::in),fout("ctc.out",ios::out);

int n,m,nrniv,l[DX],niv[DX],apst[DX];
typedef vector<int> TI;
typedef stack<int> SI;
vector<TI> cc;
TI v[DX],c;
SI st;

void tarjan(int nod);
void citire();

int main()
{
    int i;
    citire();
    for(i=1;i<=n;i++)
    {
        if(niv[i]==0)
        {
            nrniv=0;
            while(!st.empty()) st.pop();
            tarjan(i);
        }
    }
    fout<<cc.size()<<"\n";
    for(auto x: cc)
    {
        for(auto y:x)
        {
            fout<<y<<" ";
        }
        fout<<"\n";
    }
}
void tarjan(int nod)
{
    if(niv[nod]!=0) return ;
    nrniv++;
    niv[nod]=l[nod]=nrniv;
    int a;
    apst[nod]=1;
    st.push(nod);
    for(auto x:v[nod])
    {
        if(niv[x]==0)
        {
            tarjan(x);
            l[nod]=min(l[nod],l[x]);
        }
        else
        {
            if(apst[x]==1) //sa fie back-edge nu cross-edge(sa fie inca in stiva
            {
                l[nod]=min(l[nod],niv[x]);//niv in loc de l
            }
        }
    }
    if(l[nod]==niv[nod])
    {
        c.clear();
        do
        {
            a=st.top();st.pop();
            apst[a]=0;
            c.push_back(a);
        }while(!st.empty() && a!=nod);
        cc.push_back(c);
    }
}
void citire()
{
    int a,b,i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
    }
}