Cod sursa(job #3269212)

Utilizator axetyNistor Iulian axety Data 18 ianuarie 2025 13:58:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <set>
#include <stack>

#define nmax 100001
#define Inf 1000000000
using namespace std;

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

int n, m, k;
vector<int> Graf[nmax];
vector<set<int>> Rez;
int low[nmax], instack[nmax];
stack<int> nodes;
void dfs(int node)
{
    low[node] = ++m;
    int original = m;
    nodes.push(node);
    instack[node] = 1;
    for (auto i : Graf[node])
    {
        if (!low[i])
        {
            dfs(i);
        }
        if (instack[i])
        {
            low[node] = min(low[node], low[i]);
        }
    }
    if (low[node] == original)
    {
        Rez.push_back({});
        while (!nodes.empty())
        {
            Rez.back().insert(nodes.top());
            instack[nodes.top()] = 0;
            if (nodes.top() == node)
            {
                nodes.pop();
                break;
            }
            else
                nodes.pop();
        }
    }
}
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        Graf[a].push_back(b);
    }
    m = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!low[i])
        {
            dfs(i);
        }
    }
    fout << Rez.size() << '\n';
    for (auto i : Rez)
    {
        for (auto j : i)
            fout << j << " ";
        fout << '\n';
    }
    return 0;
}