Cod sursa(job #2663893)

Utilizator denisa.iordacheIordache Denisa-Elena denisa.iordache Data 27 octombrie 2020 16:04:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define maxi 100010
using namespace std;

vector<int> G[maxi];
vector<vector<int>> sol;
stack<int> s;
int N,M;
vector<int>lowlink(maxi,-1);
vector<int>disc(maxi,-1);
vector<bool>onStack(maxi,false);


void DFS(int x) {
    static int index = 0;
    disc[x] = lowlink[x] = index;
    index++;
    s.push(x);
    onStack[x] = true;

    for (int elem : G[x]) {
        if (disc[elem] == -1)
            DFS(elem);
        if (onStack[elem])
            lowlink[x] = min(lowlink[x], lowlink[elem]);
    }
    if (disc[x] == lowlink[x]) {
        vector<int> aux;

        while (s.top() != x) {
            aux.push_back(s.top());
            onStack[s.top()] = 0;
            s.pop();
        }

        aux.push_back(s.top());
        onStack[s.top()] = 0;
        s.pop();

        sol.push_back(aux);
    }
}
int main()
{

    ifstream f ("ctc.in");
    ofstream g("ctc.out");

    f>> N >>M;
    int x,y;
    for( int i = 0; i < M; i++ )
    {
        f>>x>>y;
        G[x].push_back(y);

    }




    for(int i = 1; i <=N; i++)
        if ( disc[i] == -1)
            DFS(i);


    g << sol.size() << "\n";
    for (auto vec : sol){
        for (int x : vec)
            g<< x  << " ";
        g << "\n";
    }
    return 0;
}