Cod sursa(job #3252944)

Utilizator ElideMaria Popescu Elide Data 31 octombrie 2024 16:06:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

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

vector<bool> viz;

void Dfs(int nod, vector<vector<int>>& g, vector<int>& rez)
{
    viz[nod] = 1;
    for(int i = 0; i < g[nod].size(); i++)
    {
        int vecin = g[nod][i];
        if(viz[vecin] == 0)
        {
            Dfs(vecin, g, rez);
        }
    }
    rez.push_back(nod);
}

int main()
{
    int n, m, i, j, a, b;
    vector<vector<int>> g, gt, ctc;
    vector<int> sort_t;
    in >> n >> m;
    viz.resize(n + 1);
    g.resize(n + 1);
    gt.resize(n + 1);
    for(i = 1; i <= m; i++)
    {
        in >> a >> b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }
    for(i = 1; i <= n; i++)
    {
        if(viz[i] == 0)
        {
            Dfs(i, g, sort_t);
        }
    }
    viz.clear();
    viz.resize(n + 1, 0);
    for(i = n-1; i >= 0; i--)
    {
        if(viz[sort_t[i]] == 0)
        {
            ctc.resize(ctc.size()+1);
            Dfs(sort_t[i], gt, ctc.back());
            sort(ctc.back().begin(), ctc.back().end());
        }
    }
    out << ctc.size() << '\n';
    for(i = 0; i < ctc.size(); i++)
    {
        for(j = 0; j < ctc[i].size(); j++)
        {
            out << ctc[i][j] << " ";
        }
        out << '\n';
    }
    return 0;
}