Cod sursa(job #3316906)

Utilizator anto_vscAntonia Voinescu anto_vsc Data 21 octombrie 2025 13:35:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// DFS + nr elemente conexe

vector<int> L[100001];
// int viz[100001];


// void DFS(int i, int &nr){
//     viz[i] = 1;
//     for(int j = 0; j < L[i].size(); j++){
//         int vecin = L[i][j];
//         if(viz[vecin] == 0){
//             DFS(vecin, nr);
//         }
//     }
// }


// int main()
// {
//     ifstream cin("dfs.in");
//     ofstream cout("dfs.out");

//     int n, m;
//     cin>>n>>m;
//     int x, y;
//     while (cin >> x >> y) {
//         L[x].push_back(y);
//         L[y].push_back(x);
//     }

//     int nr=0;

//     for(int i = 1; i <= n; i ++)
//     {
//         if(!viz[i])
//             DFS(i, ++nr);
//     }

//     cout<<nr;

//     return 0;
// }


//BFS


// int dist[100001];

// void BFS(int s){

//     for(int j = 0; j < L[s].size(); j++){
//         int vecin = L[s][j];

//     }
// }


// int main(){

//     ifstream fin("bfs.in");
//     ofstream fout("bfs.out");

//     int n, m, s;
//     fin>>n>>m>>s;
//     int x, y;
//     while (fin >> x >> y) {
//         L[x].push_back(y);
//     }

//     std::priority_queue<int> coada;

//     for(int j = 0; j < L[s].size(); j++){
//         coada.push(L[s][j]);
//     }



// }

//Tare conexitate


int vis1[100001];
int vis2[100001];
vector<int> LT[100001];
vector<int> v;
vector<int> ctc[100001];
int nr;

void dfs1(int nod){
    vis1[nod] =1;
    for(auto vecin: L[nod]){
        if(!vis1[vecin]){
            dfs1(vecin);
        }
    }
    v.push_back(nod);
}

void dfs2(int nod){
    ctc[nr].push_back(nod);
    vis2[nod]=1;
    for(auto vecin : LT[nod]) {
        if(!vis2[vecin]) {
            dfs2(vecin);
        }
    }

}

int main(){
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    int n, m;
    cin >>n>>m;
    for(int i=1; i<=m; i++){
        int x,y;
        cin>>x>>y;
        L[x].push_back(y);
        LT[y].push_back(x);
    }

    for(int i=1; i<=n; i++){
        if(!vis1[i]){
            dfs1(i);
        }
    }

    for(int i=v.size()-1; i>=0; i--){
        if(vis2[v[i]]){
            nr++;
            dfs2(v[i]);
        }
    }

    cout<<nr<<'\n';
    for(int i=1; i<=nr; i++){
        for(int j=0; j<ctc[i].size(); j++){
            cout<<ctc[i][j]<<" ";
        }
        cout<<'\n';
    }

    return 0;
}