Cod sursa(job #3294354)

Utilizator jumaracosminJumara Cosmin-Mihai jumaracosmin Data 21 aprilie 2025 22:18:24
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

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

//#define fin std::cin 
//#define fout std::cout 

const int NMAX = 1e5 + 5;

int n, m, ctc_count;
std::vector<int> G[NMAX], T[NMAX];
std::vector<int> ctc[NMAX];
bool visited[NMAX], visited1[NMAX];
int in_deg[NMAX];

std::stack<int> st;

void dfsT(int node)
{
    visited1[node] = true;
    ctc[ctc_count].push_back(node);
    for(auto adj : T[node])
        if(!visited1[adj])
            dfsT(adj);
}

void dfs(int node)
{
    visited[node] = true;
    for(auto adj : G[node])
        if(!visited[adj])
            dfs(adj);
    st.push(node);
}

int main() 
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        T[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i)
        if(!visited[i])
            dfs(i);

    
    while(!st.empty())
    {
        int node = st.top();
        st.pop();

        if(!visited1[node])
        {
            ctc_count++;
            dfsT(node);
        }
    }

    fout << ctc_count << "\n";
    for(int i = 1; i <= ctc_count; ++i, fout << "\n")
        for(auto node : ctc[i])
            fout << node << " ";

    return 0;
}