Cod sursa(job #3148277)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 30 august 2023 17:02:59
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

#define cin fin
#define cout fout
#define NMAX

using namespace std;

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

int n, m, nr, cnt;
stack<int> st;
vector<int> g[100001], gt[100001];
vector<int> rasp[100001];
bool viz[110];

void dfs(int nod) {
    viz[nod] = 1;
    for (auto &vecin: g[nod]) {
        if (!viz[vecin])
            dfs(vecin);
    }
    st.push(nod);
}

void dfs2(int nod) {
    viz[nod] = 1;
    for (auto &vecin: gt[nod]) {
        if (!viz[vecin])
            rasp[nr].push_back(vecin), dfs2(vecin);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (!viz[i])
            dfs(i);
    }
    for (int i = 1; i <= n; i++) {
        viz[i] = 0;
    }
    while (!st.empty()) {
        int varf = st.top();
        st.pop();
        if (!viz[varf]) {
            nr++;
            rasp[++cnt].push_back(varf);
            dfs2(varf);
        }
    }
    cout << nr << '\n';
    for (int i = 1; i <= nr; i++) {
        for (int j = 0; j < rasp[i].size(); j++) {
            cout << rasp[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}