Cod sursa(job #2891103)

Utilizator mateitudordmDumitru Matei mateitudordm Data 17 aprilie 2022 15:46:53
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100000

using namespace std;

int f[nmax + 1], nr;
vector<int> ad[nmax + 1], adrev[nmax + 1], ctc[nmax + 1];
stack<int> s;
void dfs1 (int nod)
{
    for (auto urm : ad[nod])
        if (f[urm] == 0)
            f[urm] = 1, dfs1 (urm);
    s.push (nod);
}
void dfs2 (int nod)
{
    ctc[nr].push_back (nod);
    for (auto urm : adrev[nod])
        if (f[urm] == 0)
            f[urm] = 1, dfs2 (urm);
}


int main()
{
    ifstream cin ("ctc.in");
    ofstream cout ("ctc.out");
    int n, m, i, a, b;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
        cin >> a >> b, ad[a].push_back (b), adrev[b].push_back (a);
    for (i = 1; i <= n; i++)
        if (f[i] == 0)
            f[i] = 1, dfs1 (i);
    for (i = 1; i <= n; i++)
        f[i] = 0;
    while (!s.empty())
    {
        if (f[s.top()] == 0)
            f[s.top()] = 1, ++nr, dfs2 (s.top());
        s.pop();
    }
    cout << nr << '\n';
    for (i = 1; i <= nr; i++)
    {
        for (auto a : ctc[i])
            cout << a << ' ';
        cout << '\n';
    }
    return 0;
}