Cod sursa(job #2513638)

Utilizator GBearUrsu Ianis-Vlad GBear Data 23 decembrie 2019 16:05:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
#define MAX_N 100000 + 7
using namespace std;

int N, M;
vector<vector<int>> graph(MAX_N, vector<int>());

int id[MAX_N], id_distribution = 0, low_link_value[MAX_N];

bool visited[MAX_N], onStack[MAX_N] ;

stack<int> node_stack;

vector<vector<int>> answer;

void DFS(int node)
{
    visited[node] = true;

    id[node] = low_link_value[node] = ++id_distribution;

    node_stack.push(node);
    onStack[node] = true;

    for(auto& next : graph[node])
    {
        if(visited[next] == false)
            DFS(next);

        if(onStack[next] == true)
            low_link_value[node] = min(low_link_value[node], low_link_value[next]);
    }

    if(low_link_value[node] == id[node])
    {
        answer.push_back(vector<int>());

        while(node_stack.top() != node)
        {
            answer.back().push_back(node_stack.top());
            onStack[node_stack.top()] = false;
            node_stack.pop();
        }

        node_stack.pop();
        onStack[node] = false;
        answer.back().push_back(node);
    }
}

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

    fin >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int x, y;

        fin >> x >> y;

        graph[x].push_back(y);
    }

    for(int i = 1; i <= N; ++i)
    {
        if(visited[i] == false)
        {
            DFS(i);
        }
    }

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

    for(auto& ctc : answer)
    {
        for(auto& node : ctc)
        {
            fout << node << " ";
        }

        fout << '\n';
    }
}