Cod sursa(job #3334635)

Utilizator DinVinEmanuel DinVin Data 18 ianuarie 2026 19:26:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
//lab 1
//dfs
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
vector<vector<int>> M;
int v[100001];
int n,m;
//viz start
//pt toti vecinii nevizitati, fac dfs
void dfs(int k) {
    v[k]=1;
    for (int i=0;i<M[k].size();i++) {
        int x = M[k][i];
        if (!v[x] && x)
            dfs(x);
    }
}
int main() {
    fin>>n>>m;
    M.resize(n+1);
    for (int i=1;i<=m;i++) {
        int x,y;
        fin>>x>>y;
        M[x].push_back(y);
        M[y].push_back(x);
    }
    int c = 0;
    for (int i=1;i<=n;i++) {
        if (v[i]==0) {
            dfs(i);
            c++;
        }

    }
    fout<<c;

    return 0;
}







//bfs
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <queue>
// using namespace std;
// ifstream fin ("bfs.in");
// ofstream fout ("bfs.out");
// int n,m,s;
// vector<vector<int>> M;
// int viz[100001];
// int cost[100001];
// // fac Q, push start si viz start
// // cat timp Q. iau din Q, afisez
// // pt fiecare vecin, daca nu-i viz, viziteaza-l si da-i push
//
// void bfs(int start) {
//     queue<int> Q;
//     Q.push(start);
//     viz[start] = 1;
//     cost[start] = 0;
//     while (!Q.empty()) {
//         int k = Q.front(); Q.pop();
//         for (int i=0;i<M[k].size();i++) {
//             int x = M[k][i];
//             if (!viz[x]) {
//                 viz[x]=1;
//                 cost[x] = cost[k]+1;
//                 Q.push(x);
//             }
//         }
//     }
// }
//
// int main() {
//     fin>>n>>m>>s;
//     M.resize(n+1);
//     for (int i=1;i<=m;i++) {
//         int x,y;
//         fin>>x>>y;
//         M[x].push_back(y);
//     }
//     for (int i=1;i<=n;i++)cost[i]=-1;
//     bfs(s);
//     for (int i=1;i<=n;i++)fout<<cost[i]<<' ';
//     return 0;
// }