Cod sursa(job #3286598)

Utilizator Allie28Radu Alesia Allie28 Data 14 martie 2025 13:48:09
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int LMAX = 200005;
const int MOD = 1000000007;
const int INF = 0x3F3F3F3F;

vector<int> L[LMAX], LT[LMAX], order, comp[LMAX];
vector<bool> viz;

void dfs(int node) {
    viz[node] = 1;
    for (int vec : L[node]) {
        if (!viz[vec]) dfs(vec);
    }
    order.push_back(node);
}

void dfs2(int node, int nr_comp) {
    viz[node] = 1;
    comp[nr_comp].push_back(node);
    for (int vec : LT[node]) {
        if (!viz[vec]) {
            dfs2(vec, nr_comp);
        }
    }
}


int main() {
    int n, m, i;
    fin>>n>>m;
    while (m--) {
        int x, y;
        fin>>x>>y;
        L[x].push_back(y);
        LT[y].push_back(x);
    }
    viz.assign(n + 5, 0);
    //sortez topologic
    for (i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfs(i);
        }
    }
    reverse(order.begin(), order.end());
    viz.assign(n + 5, 0);
    int nr_comp = 1;
    for (i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfs2(i, nr_comp);
            if (comp[nr_comp].size() > 1) {
                nr_comp++;
            }
            else {
                comp[nr_comp].pop_back();
            }
        }
    }
    fout<<nr_comp - 1<<"\n";
    for (i = 1; i < nr_comp; i++) {
        for (int vec : comp[i]) {
            fout<<vec<<" ";
        }
        fout<<"\n";
    }





    fin.close();
    fout.close();
    return 0;
}