Cod sursa(job #3320263)

Utilizator RaluccccaNegru Raluca Ralucccca Data 4 noiembrie 2025 19:20:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

void DFS(int start, vector<vector<int>> &L, vector<int> &viz, stack<int> &st) {
    viz[start]=1;
    for (const auto vecin : L[start]) {
        if (viz[vecin]==0) {
            DFS(vecin, L, viz, st);
        }
    }
    st.push(start);
}

void DFST(int start, vector<vector<int>> &L_t, vector<int> &viz, vector<int> &v) {
    viz[start]=1;
    v.push_back(start);
    for (const auto vecin : L_t[start]) {
        if (viz[vecin] ==0) {
            DFST(vecin, L_t, viz, v);
        }
    }
}

int main() {
    int n, m, x, y;
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin>>n>>m;
    vector<vector<int>> L(n+1), L_t(n+1);
    vector<int> viz(n+1,0);
    stack<int> st;
    for (int i=0; i<m; i++) {
        fin>>x>>y;
        L[x].push_back(y);
        sort(L[x].begin(), L[x].end());
        L_t[y].push_back(x);
        sort(L_t[y].begin(), L_t[y].end());
    }
    for (int i=1; i<=n; i++) {
        
        if (viz[i] == 0) {
            DFS(i, L, viz, st);
        }
    }
    viz.assign(n+1,0);
    vector<vector<int>> ctc;

    while (st.size()!=0) {
        int vf = st.top();
        st.pop();
        if (viz[vf] == 0) {
            vector<int> v;
            DFST(vf, L_t, viz,v);
            ctc.push_back(v);
        }
    }
    fout<<ctc.size()<<"\n";
    for (const auto vector : ctc) {
        for (int x : vector) {
            fout<<x<<" ";
        }
        fout<<"\n";
    }

    return 0;
}