Cod sursa(job #2923655)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 17 septembrie 2022 14:49:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

/*******************************/
// INPUT / OUTPUT

ifstream f("ctc.in");
ofstream g("ctc.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N, M;
int id;
int ids[NMAX], low[NMAX];
bool in_stack[NMAX];
stack <int> s;
vector <int> adj[NMAX];
vector <vector < int > > ctc;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> N >> M;

    int a, b;
    for (int i = 1 ; i <= M ; ++ i)
    {
        f >> a >> b;
        adj[a].push_back(b);
    }
}
///-------------------------------------
void dfs(int node)
{
    ids[node] = low[node] = ++id;
    in_stack[node] = true;
    s.push(node);

    for (auto u: adj[node])
    {
        if (!ids[u]) dfs(u); 
        if (in_stack[u]) low[node] = min(low[node], low[u]);
        
    }

    if (low[node] == ids[node])
    {
        int top;
        vector <int> v;
        do {
            top = s.top();
            s.pop();
            in_stack[top] = false;
            v.push_back(top);
        } while (top != node);
        ctc.push_back(v);
    }
}
///-------------------------------------
inline void Solution()
{
    for (int i = 1 ; i <= N ; ++ i)
    {
        if (!ids[i]) dfs(i);
    }
}
///-------------------------------------
inline void Output()
{
    g << ctc.size() << "\n";

    for (auto v: ctc)
    {
        for (auto x: v)
            g << x << " ";
        g << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}