Cod sursa(job #2665059)

Utilizator miramaria27Stroie Mira miramaria27 Data 29 octombrie 2020 22:56:02
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <list>
#include <stack>
#include <fstream>
#include <algorithm>


using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
int nr = 0;
int dis = 0; /// the number of discovery
void dfs(int start, list<int> ad[],int d[], int onstack[], list <int> rez[], int low[], stack <int> &st)
{


    ///housekeeping stuff :)
    d[start] = low[start] = ++ dis;
    onstack[start] = 1;
    st.push(start);

    for(auto &child : ad[start])
    {
        if(d[child] == 0)
           {
              dfs(child,ad,d,onstack,rez,low,st);
           }
        ///on callback
        if(onstack[child] == 1)
             low[start] = min(low[start],low[child]);

    }
    ///after we visited all neighbours
    if(d[start] == low[start])
    {
        ///hopa! it seems that the current node starts a SCC!
        nr ++;
        while(st.top() != start)
        {
            rez[nr].push_front(st.top());
            st.pop();
            onstack[start] = 0;

        }
        rez[nr].push_front(st.top());
        st.pop();

    }
}
int main()
{
    int n,m,start;
    fin>>n>>m;
    list <int> ad[n+1];

    for(int i = 0; i < m; i ++)
    {

        int x,y;
        fin >> x >> y;
        ad[x].push_back(y);


    }
    int d[n+1] = {0};
    int onstack[n+1] = {0};
    int low[ n + 1] = {0};
    stack <int> st;
    list <int> rez[ n + 1];

    for(int i=1; i<=n; i++)
            if(d[i] == 0)
            {
                start = i;
                dfs(start,ad,d,onstack,rez,low,st);
            }
    fout << nr<<"\n";
    for(int i = 1; i <= nr ; i ++)
    {
        for(auto &it: rez[i])
            fout<<it<<" ";
        fout<<"\n";

    }
    return 0;
}