Cod sursa(job #1923531)

Utilizator carla_rbbCarla Popescu carla_rbb Data 11 martie 2017 14:41:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
//descompunerea unui graf in componente tare conexe
// Tarjan algorithm
//worst case complexity: O(n+m), n-nr noduri, m-nr de arce
#include <bits/stdc++.h>

using namespace std;

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

int idx[100010],mini[100010],ssc,a,b,x,y,n,m,i,instack[100010];
stack <int> st;
vector <int> G[100010],CTC[100010];

void DFS (int nod)
{
    //idx-> pastreaza ordinea in care sunt descoperite nodurile
    //mini[nod]=cel mai mic index la care se poate ajunge din nod
    //v trebuie pastrat in stiva dupa ce a fost vizitat <=> mini[v]<idx[v]
    mini[nod] = idx[nod] = ++idx[0];
    instack[nod]=1;
    st.push(nod);
    for(auto it: G[nod])
    {
        if(!idx[it])DFS(it);
        if(instack[it])
            mini[nod]=min (mini[nod], mini[it]);
    }

     // If v is a root node, pop the stack and generate a SCC
    if(mini[nod] == idx[nod])
    {
        ++ssc; //start a new strongly connected component
        while(st.top()!=nod)
        {
            CTC[ssc].push_back( st.top() );
            instack[ st.top() ]=0;//add w to current strongly connected component
            st.pop();
        }
        CTC[ssc].push_back( st.top() );
        instack[nod]=0;
        st.pop();
    }
}

int main()
{

    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
    }

    for(i=1; i<=n; i++)
    {
        if(!idx[i])
            DFS(i);

    }
//    for(i=1;i<=n;i++)cout<<idx[i]<<" ";
//    cout<<endl;
//    for(i=1;i<=n;i++)cout<<mini[i]<<" ";
//    cout<<endl;
    fout<<ssc<<'\n';
    for(i=1; i<=ssc; i++)
    {
        for(auto it: CTC[i])
                fout<<it<<" ";
        fout<<'\n';
    }
    return 0;
}