Cod sursa(job #2980661)

Utilizator Elvis_CostinTuca Elvis-Costin Elvis_Costin Data 16 februarie 2023 18:29:10
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;
string np = "ctc";
ifstream f(np + ".in");
ofstream g(np + ".out");

// #define f cin
// #define g cout

int n, m, len;
vector<int> adj[100003], adjr[100003], rez[100003], order;
vector<bool> viz;

void dfs1(int nod)
{
    viz[nod] = 1;
    for (auto next : adj[nod])
        if (!viz[next])
            dfs1(next);
    order.push_back(nod);
}
void dfs2(int nod, int k)
{
    viz[nod] = 1;
    rez[k].push_back(nod);
    for (auto next : adj[nod])
        if (!viz[next])
            dfs2(next, k);
}
int main()
{
    f >> n >> m;
    for (int i = 1, a, b; i <= m; i++)
        f >> a >> b, adj[a].push_back(b), adjr[b].push_back(a);

    viz.assign(n + 1, 0);
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs1(i);

    viz.assign(n + 1, 0);
    for (auto u : order)
        if (!viz[u])
            dfs2(u, ++len);

    g << len << '\n';
    for (int i = 1; i <= len; i++, g << '\n')
        for (auto x : rez[i])
            g << x << " ";

    return 0;
}