Cod sursa(job #2474125)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 14 octombrie 2019 19:07:56
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
#define N_MAX 100000
using namespace std;

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

int n, m;

vector<vector<int>> graph(N_MAX, vector<int>());

vector<vector<int>> sol;

vector<bool> onStack(N_MAX, false);
vector<bool> visited(N_MAX, false);
vector<int> id(N_MAX);
vector<int> low(N_MAX);

stack<int> Stack;

int t = 0;

void find_ctc(int node)
{
    visited.at(node) = true;

    ++t;
    id.at(node) = t;
    low.at(node) = t;

    Stack.push(node);
    onStack.at(node) = true;

    for(auto& next : graph.at(node))
    {
        if(visited.at(next) == false) find_ctc(next);

        if(onStack.at(next) == true) low.at(node) = min(low.at(node), low.at(next));
    }


    if(low.at(node) == id.at(node))
    {
        vector<int> ctc;

        while(Stack.top() != node)
        {
            onStack.at(Stack.top()) = false;
            ctc.push_back(Stack.top());
            Stack.pop();
        }

        onStack.at(Stack.top()) = false;
        ctc.push_back(Stack.top());
        Stack.pop();

        sol.push_back(ctc);
    }


}

int main()
{
    fin >> n >> m;

    for(int x, y, i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        graph.at(x).push_back(y);
    }

    for(int i = 1; i <= n; ++i)
    {
        if(visited.at(i) == false)
        {
            find_ctc(i);
        }
    }

    fout << sol.size() << '\n';

    for(auto& ctc : sol)
    {
        for(auto& node : ctc) fout << node << ' ';
        fout << '\n';
    }
}