Cod sursa(job #2926944)

Utilizator AswVwsACamburu Luca AswVwsA Data 18 octombrie 2022 22:58:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 200001;
vector <vector <int> > sol;

vector <int> g[NMAX][2];

vector <int> stiva;
bool viz[NMAX][2];

void dfs(int nod, int unde, vector <int> &save)
{
    viz[nod][unde] = 1;
    for (int aux : g[nod][unde])
        if (!viz[aux][unde])
            dfs(aux, unde, save);
    save.push_back(nod);
}
int main()
{
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    int n, m, i, j;
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        g[a][0].push_back(b);
        g[b][1].push_back(a);
    }
    for (i = 1; i <= n; i++)
        if (!viz[i][0])
            dfs(i, 0, stiva);
/*    for (i = 0; i < stiva.size(); i++)
        cout << stiva[i] << " ";
    cout << '\n';*/
    for (i = stiva.size() - 1; i > -1; i--)
        if (!viz[stiva[i]][1])
        {
            vector <int> aux;
            dfs(stiva[i], 1, aux);
            sol.push_back(aux);
        }
    cout << sol.size() << "\n";
    for (i = 0; i < sol.size(); i++, cout << "\n")
        for (j = 0; j < sol[i].size(); j++)
            cout << sol[i][j] << " ";
}