Cod sursa(job #2435417)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 3 iulie 2019 22:34:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#define NMAX 100005

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

list<int> G[NMAX];
int index[NMAX], min_reach[NMAX], ct;
bool viz[NMAX];
stack<int> st;
list<int> cc[NMAX];

void connect(int x){
    int y;
    index[x] = min_reach[x] = ++index[0];
    viz[x] = 1;
    st.push(x);

    list<int>::iterator it;
    for(it = G[x].begin(); it != G[x].end(); it++){
        y = *it;
        if(!index[y]){
            connect(y);
            min_reach[x] = min(min_reach[x], min_reach[y]);
        }
        else if(viz[y]){
            min_reach[x] = min(min_reach[x], index[y]);
        }
    }

    if(index[x] ==  min_reach[x]){
        ct++;y = 0;
        while(y != x){
            y = st.top();
            st.pop(); viz[y] = 0;
            cc[ct].push_back(y);
        }
    }
}

int main()
{
    int n, m, i, x, y;

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

    index[0] = 0;
    for(i = 1; i <= n; i++)
        if(!index[i]) connect(i);

    fout << ct << "\n";
    for(i = 1; i <= ct; i++){
        while(!cc[i].empty()){
            fout << cc[i].back() << " ";
            cc[i].pop_back();
        }
        fout << "\n";
    }

    return 0;
}