Cod sursa(job #2663246)

Utilizator denisa.iordacheIordache Denisa-Elena denisa.iordache Data 25 octombrie 2020 18:10:52
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
const int maxi = 100010;

using namespace std;

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

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




void DFS(int node)
{
    static int index = 0;
    disc[node] = lowlink[node] = index;
    index++;
    s.push(node);
    onStack[node]=true;
    for (int it : G[node])
    {
        if (disc[it]==-1)   ///daca nodul nu e vizitat, parcurgem in adancime
        
            DFS(it);



        if (onStack[it]==true)  ///back-end edge

            lowlink[node] = min (lowlink[node],lowlink[it]);

    }

    if (lowlink[node] == disc[node]) ///inceputul unei componente tare conexe
    {
        vector <int> v;
        while(s.top()!=node)
        {
            v.push_back(s.top());
            onStack[s.top()] == false;
            s.pop();
        }
        v.push_back(node);
        onStack[node] = false;
        s.pop();

        sol.push_back(v);
    }

}

int main()
{

    f>>N;
    f>>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++)
    {cout<<i<<":";
        for(int x: G[i])
            cout<<x<<" ";
        cout<<endl;}*/

    for(int i=1;i<=N;i++)
    {
        lowlink[i] = -1;
        disc[i] = -1;
        onStack[i] = false;
    }

    for(int i=1;i<=N;i++)
        if(disc[i] == -1)
            DFS(i);
    g<<sol.size()<<'\n';
    for(auto i: sol)
    {for(auto elem:i)
            g<<elem<<" ";
        g<<'\n';}


    return 0;
}