Cod sursa(job #3041176)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 31 martie 2023 09:32:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

constexpr int NMAX = 1e5 + 1;

vector<int> vecinit[NMAX];
vector<int> vecini[NMAX]; int comp[NMAX],nr;
vector<vector<int>> ans;
bool viz[NMAX]; stack<int> top;

void dfs(int nod)
{
    viz[nod] = 1;
    for(auto it : vecini[nod])
        if(!viz[it]) dfs(it);
    top.push(nod);
}

void trans(int nod)
{
    comp[nod] = nr;
    for(auto it : vecinit[nod])
        if(!comp[it])
            trans(it);

    ans.back().emplace_back(nod);
}

int main()
{
    int n,m,a,b,c; cin >> n >> m;
    for(int i = 1; i <= m ; i++)
        {
            cin >> a >> b;
            vecini[a].emplace_back(b);
            vecinit[b].emplace_back(a);
        }

    for(int i = 1; i <= n ; i++) if(!viz[i]) dfs(i);
    while(!top.empty())
        {
            int v = top.top(); top.pop();
            if(comp[v]) continue;
            else
                {
                    ans.push_back({});
                    nr++; trans(v);
                }
        }

    cout << ans.size() << '\n';
    for(auto it : ans)
        {
            for(auto j : it) cout << j << " ";
            cout << '\n';
        }
}