Cod sursa(job #3337760)

Utilizator ccris.29Chirila Cristian ccris.29 Data 29 ianuarie 2026 19:45:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

int n, m, a, b, vis[100001], ct;
vector<int> AD[100001], ADT[100001], comp[100001];
stack<int> s;

void DFS(int nod)
{
    vis[nod] = 1;

    for (int i = 0; i < AD[nod].size(); i++)
    {
        int w = AD[nod][i];

        if (vis[w] == 0)
            DFS(w);
    }
    s.push(nod);
}
void DFST(int nod)
{
    vis[nod] = 2;

    for (int i = 0; i < ADT[nod].size(); i++)
    {
        int w = ADT[nod][i];

        if (vis[w] == 1)
        {
            DFST(w);
        }
    }
    comp[ct].push_back(nod);
}
int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> a >> b;
        AD[a].push_back(b);
        ADT[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
        if (vis[i] == 0)
            DFS(i);

    while (s.size() != 0)
    {
        int i = s.top();
        s.pop();

        if (vis[i] == 1)
        {
            ct++;
            DFST(i);
        }
    }

    fout << ct;

    for (int i = 1; i <= ct; i++)
    {
        fout << "\n";
        for (int j = 0; j < comp[i].size(); j++)
            fout << comp[i][j] << " ";
    }

    return 0;
}