Cod sursa(job #2927378)

Utilizator 4N70N1U5Antonio Nitoi 4N70N1U5 Data 20 octombrie 2022 11:30:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

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

int n, m, c = 0;
vector<bool> vis, vis_tr;
vector< vector<int> > adj, adj_tr;
vector<string> out;
stack<int> s;

void dfs_order(int v)
{
    vis[v] = true;

    for (int i = 0; i < adj[v].size(); i++)
    {
        if (!vis[adj[v][i]])
        {
            dfs_order(adj[v][i]);
        }
    }

    s.push(v);
}

void dfs(int v)
{
    vis_tr[v] = true;
    out[c] += to_string(v) + ' ';

    for (int i = 0; i < adj_tr[v].size(); i++)
    {
        if (!vis_tr[adj_tr[v][i]])
        {
            dfs(adj_tr[v][i]);
        }
    }
}

int main()
{
    fin >> n >> m;

    adj.resize(n + 1);
    adj_tr.resize(n + 1);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj_tr[y].push_back(x);
    }

    vis.resize(n + 1, false);
    vis_tr.resize(n + 1, false);

    for (int v = 1; v <= n; v++)
    {
        if (!vis[v])
        {
            dfs_order(v);
        }
    }

    while (!s.empty())
    {
        int v = s.top();
        s.pop();

        if (!vis_tr[v])
        {
            out.push_back("");
            dfs(v);
            c++;
        }
    }

    fout << c << '\n';

    for (int i = 0; i < c; i++)
    {
        fout << out[i] << '\n';
    }
}