Cod sursa(job #3327272)

Utilizator ariscoiZaharia Aris ariscoi Data 2 decembrie 2025 23:20:24
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.79 kb
// #include <iostream>
// #include <vector>
// #include <deque>
// using namespace std;
//
// int main() {
//     int n, m, G;
//     cin >> n >> m >> G;
//
//     vector<vector<pair<int,int>>> adj(n + 1);
//     vector<int> dist(n + 1, 1e9);
//
//     for (int i = 0; i < m; i++) {
//         int u, v, g;
//         cin >> u >> v >> g;
//
//         int cost = (g >= G ? 0 : 1);
//
//         adj[u].push_back({v, cost});
//         adj[v].push_back({u, cost});
//     }
//
//     deque<int> dq;
//     dist[1] = 0;
//     dq.push_front(1);
//
//     while (!dq.empty()) {
//         int nod = dq.front();
//         dq.pop_front();
//
//         for (auto &edge : adj[nod]) {
//             int vecin = edge.first;
//             int cost = edge.second;
//
//             if (dist[nod] + cost < dist[vecin]) {
//                 dist[vecin] = dist[nod] + cost;
//
//                 if (cost == 0)
//                     dq.push_front(vecin);
//                 else
//                     dq.push_back(vecin);
//             }
//         }
//     }
//
//     cout << dist[n] << "\n";
//     return 0;
// }

/*!!!!!!!!!!!!!!!*/
// #include <algorithm>
// #include <iostream>
// #include <vector>
// #include <fstream>
// #include <queue>
// #include <deque>
// using namespace std;
//
// int main() {
//     int n, m, G;
//     cin >> n >> m >> G;
//
//     vector<vector<pair<int,int>>> adj(n + 1);
//     vector<int> dist(n + 1, 1e9);
//
//     for (int i = 0; i < m; i++) {
//         int u, v, g;
//         cin >> u >> v >> g;
//
//         int cost = (g >= G ? 0 : 1);
//
//         adj[u].push_back({v, cost});
//         adj[v].push_back({u, cost});
//     }
//
//     deque<int> dq;
//     dist[1] = 0;
//     dq.push_front(1);
//
//     while (!dq.empty()) {
//         int nod = dq.front();
//         dq.pop_front();
//
//         for (auto &edge : adj[nod]) {
//             int vecin = edge.first;
//             int cost = edge.second;
//
//             if (dist[nod] + cost < dist[vecin]) {
//                 dist[vecin] = dist[nod] + cost;
//
//                 if (cost == 0)
//                     dq.push_front(vecin);
//                 else
//                     dq.push_back(vecin);
//             }
//         }
//     }
//
//     cout << dist[n] << "\n";
//     return 0;
// }
//
//
// /vector<int> graf[100001];
// bool vizitat[100001];
//
// void dfs(int nod) {
//     vizitat[nod] = true;
//     for (int vecin : graf[nod]) {
//         if(!vizitat[vecin])
//             dfs(vecin);
//     }
// }
//
// int main() {
//     int N, M;
//     cin >> N >> M;
//
//     for (int i = 0; i < M; i++) {
//         int x,y;
//         cin >> x >> y;
//
//         graf[x].push_back(y);
//         graf[y].push_back(x);
//     }
//
//     int componente = 0;
//     for (int i= 0; i < N; i++) {
//         if (vizitat[i] == false) {
//             componente++;
//             dfs(i);
//         }
//     }
//
//     cout << componente << "\n";
//
//     return 0;
// }/


#include <fstream>
#include <vector>
using namespace std;

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

vector<int> visited;
vector<vector<int> > adj;
int n, m;

void DFS(int i) {
    visited[i] = 1;
    for (auto &vecin :adj[i]) {
        if (visited[vecin] == 0) {
            DFS(vecin);
        }
    }
}

int main() {
    fin >> n >> m;
    adj.resize(n);
    visited.resize(n);
    for (int i=0 ; i<m ; ++i) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int components = 0;
    for (int i=1 ; i<=n ; ++i) {
        if (visited[i] == 0) {
            components++;
            DFS(i);
        }
    }
    fout << components;
}