Cod sursa(job #2796418)

Utilizator HatersMcCristian Ioan HatersMc Data 8 noiembrie 2021 00:46:54
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;

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

int n, m, nr;
deque<int> stiva;
vector<int> viz(100001);
vector<vector<int>> sol(100001), a(100001), b(100001);


void dfs(int s) {
    viz[s] = 1;
    for (int i : a[s])
        if (!viz[i])
            dfs(i);
    stiva.push_back(s);
}

void dfsr(int s) {
    viz[s] = 2;
    sol[nr].push_back(s);
    for (int i :b[s])
        if (viz[i] == 1) dfsr(i);
}


int main() {
    int x, y;
    int val;
    f >> n >> m;
    for (int i = 0; i < m; ++i) {

        f >> x >> y;
        a[x].push_back(y);
        b[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i);

    while (!stiva.empty()) {
        val = stiva.back();
        if (viz[val] == 1) {
            nr++;
            dfsr(val);
        }
        stiva.pop_back();
    }
    g << nr;
    for (auto a : sol) {
       for(int i : a)
            g << i << " ";
        g << '\n';
    }
    return 0;
}