Cod sursa(job #2930001)

Utilizator BojneaguBojneagu David-Alexandru Bojneagu Data 27 octombrie 2022 12:03:09
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out")

vector<vector<int>> adj,res,adj_t;
vector<int> viz,lvl;

int nrn, nre, n, e, nr_res;

void first_DFS(int node)
{

    for (auto it : adj[node])
        if (viz[it] == 0)
        {
            viz[it] = 1;
            first_DFS(it);
        }
    lvl.push_back(node);

}

void second_DFS(int node)
{
    res[nr_res].push_back(node);
    viz[node] = -1;
    for (auto itt : adj_t[node])
    {
        if (viz[itt] == 1)
            second_DFS(itt);
    }
}
int main() {
    fin >> nrn >> nre;

    adj_t.resize(nrn + 1);
    adj.resize(nrn + 1);
    viz.resize(nrn + 1, 0);
    res.resize(nrn + 1);

    for (int i = 0; i < nre; i++)
    {
        fin >> n >> e;
        adj[n].push_back(e);
        adj_t[e].push_back(n);
    }

    for (int i = 1; i <= nrn; i++)
        if (viz[i] == 0)
        {
            viz[i] = 1;
            first_DFS(i);
        }
    while (!lvl.empty())
    {
        int cur = lvl.back();lvl.pop_back();
        if (viz[cur] == 1)
        {
            nr_res++;
            second_DFS(cur);
        }
    }
    fout << nr_res << endl;

    for (int i = 1; i <= nr_res; i++)
    {
        for (int j = 0; j < res[i].size(); j++)
            fout << res[i][j] << ' ';
        fout << endl;
    }

    fin.close();
    fout.close();

    return 0;

}