Cod sursa(job #3319320)

Utilizator petru-robuRobu Petru petru-robu Data 31 octombrie 2025 17:24:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<vector<int>> adj_list;
vector<vector<int>> adj_list_trans;
vector<int> cc;
vector<vector<int>> ans;
stack<int> out_st;
vector<int> visited;

void read()
{
    fin>>n>>m;

    adj_list.assign(n+1, vector<int>());
    adj_list_trans.assign(n+1, vector<int>());
    visited.assign(n+1, 0);

    for(int i=0; i<m; i++)
    {
        int x, y;
        fin>>x>>y;
        adj_list[x].push_back(y);
        adj_list_trans[y].push_back(x);
    }
}

void dfs(int x)
{
    visited[x] = 1;
    
    for(auto &next:adj_list[x])
    {
        if(!visited[next])
            dfs(next);
    }

    out_st.push(x);
}

void dfs_T(int x)
{
    cc.push_back(x);
    visited[x] = 1;
    
    for(auto &next:adj_list_trans[x])
    {
        if(!visited[next])
            dfs_T(next);
    }
}


int main()
{
    read();

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

    for(int i=1 ;i<=n; i++)
        visited[i] = 0;

    while(!out_st.empty())
    {
        int x = out_st.top();
        //cout<<x<<'\n';
        out_st.pop();

        if(!visited[x])
        {
            dfs_T(x);
            ans.push_back(cc);
            cc.clear();
        }
            
    }

    fout<<ans.size()<<'\n';
    for(auto &cc:ans)
    {
        for(auto &x:cc)
            fout<<x<<' ';
        fout<<'\n';
    }


    return 0;
}