Cod sursa(job #3331417)

Utilizator Valentincrs01Buse Valentin-Cristian Valentincrs01 Data 27 decembrie 2025 18:12:11
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.8 kb
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <fstream>

using namespace std;

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

const int NMAX = 100005;
vector<int> G[NMAX];
bool vizitat[NMAX];

void dfs(int start)
{
    stack<int> stiva;
    stiva.push(start);
    vizitat[start] = true;
    while(!stiva.empty())
    {
        int curr = stiva.top();
        stiva.pop();
        for(int vecin : G[curr])
        {
            if(!vizitat[vecin])
            {
                vizitat[vecin] = true;
                stiva.push(vecin);
            }
        }
    }
}
int main()
{
    int N, M;
    fin >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int compConexe = 0;
    for(int i = 0; i < N; i++)
    {
        if(!vizitat[i])
        {
            compConexe++;
            dfs(i);
        }
    }
    fout << compConexe << endl;
    fin.close();
    fout.close();
    return 0; 
}

// Distanta minima cu BFS
// ifstream fin("bfs.in");
// ofstream fout("bfs.out");
// const int NMAX = 100005;
// const int INF = -1;
// vector<int> G[NMAX];
// int dist[NMAX];
// int main()
// {
//     int N, M, S;
//     fin >> N >> M >> S;
//     for(int i = 0 ; i < M; i++)
//     {
//         int x, y;
//         fin >> x >> y;
//         G[x].push_back(y);
//     }
//     for(int i = 1; i <= N; i++)
//     {
//         dist[i] = INF;
//     }
//     queue<int> coada;
//     coada.push(S);
//     dist[S] = 0;
//     while(!coada.empty())
//     {
//         int curr = coada.front();
//         coada.pop();
//         for(int vecin : G[curr])
//         {
//             if(dist[vecin] == INF)
//             {
//                 dist[vecin] = dist[curr] + 1;
//                 coada.push(vecin);
//             }            
//         }
//     }
//     for(int i = 1; i <= M; i++)
//     {
//         fout << dist[i] << " ";
//     }
//     fout << endl;
//     fin.close();
//     fout.close();
//     return 0;
// }

// BFS classic
// void adaugaMuchie(vector<int> listaAdiacenta[], int u, int v)
// {
//     listaAdiacenta[u].push_back(v);
//     listaAdiacenta[v].push_back(u);
// }
// vector<int> BFS(vector<int> listaAdiacenta[], int nrNoduri, int start)
// {
//     queue<int> coada;
//     vector<int> rez;
//     vector<bool> vizitat(nrNoduri, false);
//     vizitat[start] = true;
//     coada.push(start);
//     while(!coada.empty())
//     {
//         int curr = coada.front();
//         coada.pop();
//         rez.push_back(curr);
//         for(int vecin : listaAdiacenta[curr])
//         {
//             if(!vizitat[vecin])
//             {
//                 vizitat[vecin] = true;
//                 coada.push(vecin);
//             }
//         }
//     }
//     return rez;
// }
// int main() {
//     const int nrNoduri = 7;  
//     vector<int> listaAdiacenta[nrNoduri];
//     adaugaMuchie(listaAdiacenta, 0, 1);
//     adaugaMuchie(listaAdiacenta, 0, 2);
//     adaugaMuchie(listaAdiacenta, 1, 3);
//     adaugaMuchie(listaAdiacenta, 1, 4);
//     adaugaMuchie(listaAdiacenta, 2, 5);
//     adaugaMuchie(listaAdiacenta, 4, 5);
//     vector<int> rezultatBFS = BFS(listaAdiacenta, nrNoduri, 0);
//     cout << "\nOrdinea BFS: ";
//     for (int nod : rezultatBFS) {
//         cout << nod << " ";
//     }
//     cout << endl;
//     return 0;
// }

// DFS classic
// void adaugaMuchie(vector<int> listaAdiacenta[], int u, int v)
// {
//     listaAdiacenta[u].push_back(v);
//     listaAdiacenta[v].push_back(u);
// }
// vector<int> DFS(vector<int> listaAdiacenta[], int nrNoduri, int start)
// {
//     vector<int> rez;
//     vector<bool> vizitat(nrNoduri, false);
//     stack<int> st;
//     st.push(start);
//     vizitat[start] = true;
//     while(!st.empty())
//     {
//         int curr = st.top();
//         st.pop();
//         rez.push_back(curr);
//         for(int vecin : listaAdiacenta[curr])
//         {
//             if(!vizitat[vecin])
//             {
//                 st.push(vecin);
//                 vizitat[vecin] = true;
//             }
//         }   
//     }
//     return rez;
// }
// int main() {
//     const int nrNoduri = 7;
//     vector<int> listaAdiacenta[nrNoduri];
//     adaugaMuchie(listaAdiacenta, 0, 1);
//     adaugaMuchie(listaAdiacenta, 0, 2);
//     adaugaMuchie(listaAdiacenta, 1, 3);
//     adaugaMuchie(listaAdiacenta, 1, 4);
//     adaugaMuchie(listaAdiacenta, 2, 5);
//     adaugaMuchie(listaAdiacenta, 4, 5);
//     vector<int> rezultatDFS = DFS(listaAdiacenta, nrNoduri, 0);
//     cout << "\nOrdinea DFS: ";
//     for (int nod : rezultatDFS) {
//         cout << nod << " ";
//     }
//     cout << endl;
//     return 0;
// }

// Conversie lista <-> matrice
// void listeToMatrice(int n, vector<int> adj[MAX], int a[MAX][MAX]) {
//     for (int i = 1; i <= n; i++) {
//         for (int j = 1; j <= n; j++) {
//             a[i][j] = 0;
//         }
//     }
//     for (int i = 1; i <= n; i++) {
//         for (size_t k = 0; k < adj[i].size(); k++) {
//             int v = adj[i][k];
//             a[i][v] = 1;
//         }
//     }
// }
// void matriceToListe(int n, int a[MAX][MAX], vector<int> adj[MAX]) {
//     for (int i = 1; i <= n; i++) {
//         adj[i].clear();
//     }
//     for (int i = 1; i <= n; i++) {
//         for (int j = 1; j <= n; j++) {
//             if (a[i][j] == 1) {
//                 adj[i].push_back(j);
//             }
//         }
//     }
// }

// Lista de adiacenta
// const int MAX = 10001;
// void construiesteListe(const char* numeFisier, vector<int> graf[], int &n, int tip)
// {
//     ifstream fin(numeFisier);
//     int m, x, y;
//     fin >> n >> m;
//     for(int i = 1; i <= n; i++)
//     {
//         graf[i].clear();
//     }
//     for(int i = 0; i < m; i++)
//     {
//         fin >> x >> y;
//         graf[x].push_back(y);
//         if(tip == 0)
//         {
//             graf[y].push_back(x);
//         }
//     }
//     fin.close();
// }
// void afiseazaListe(vector<int> graf[], int &n)
// {
//     for(int i = 1; i <= n; i++)
//     {
//         cout << "Nodul " << i << " are vecinii: ";
//         if(graf[i].size() == 0)
//         {
//             cout << "(niciun vecin)" << endl;
//         }
//         else
//         {
//             for(int j{0}; j < graf[i].size(); j++)
//             {
//                 cout << graf[i][j] << " ";
//             }
//             cout << endl;
//         }
//     }
// }
// int main() {
//     int n;
//     vector<int> adj[MAX];
//     cout << "--- Graf Neorientat ---" << endl;
//     construiesteListe("graf.in", adj, n, 0);
//     afiseazaListe(adj, n);
//     cout << endl;
//     cout << "--- Graf Orientat ---" << endl;
//     construiesteListe("graf.in", adj, n, 1);
//     afiseazaListe(adj, n);
//     return 0;
// }

// Matrice de adiacenta
// const int MAX = 101;
// void construiesteMatr(const char* numeFisier, int a[MAX][MAX], int &n, int tip)
// {
//     ifstream fin(numeFisier);
//     if(!fin)
//     {
//         cout << "Nu s-a putut deschide fisierul";
//         return;
//     }
//     int m;
//     fin >> n >> m;
//     for(int i = 1; i <= n; i++)
//     {
//         for(int j = 1; j <= n; j++)
//         {
//             a[i][j] = 0;
//         }
//     }
//     int x, y;
//     for(int i = 1; i <= m; i++ )
//     {
//         fin >> x >> y;
//         a[x][y] = 1;
//         if(tip == 0)
//         {
//             a[y][x] = 1;
//         }
//     }
//     fin.close();
// }
// void afisareMatr(int a[MAX][MAX], int n)
// {
//     for(int i = 1; i <= n; i++)
//     {
//         for(int j = 1; j <= n; j++)
//         {
//             cout << a[i][j] << " ";
//         }
//         cout << endl;
//     }
// }
// int main()
// {
//     int a[MAX][MAX], n;
//     construiesteMatr("graf.in", a, n, 1);
//     cout << "Matricea adiacenta este: "<< endl;
//     afisareMatr(a, n);
//     return 0;
// }