Cod sursa(job #2422921)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 20 mai 2019 12:56:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
int visited[100001];
using namespace std;
int main() {
    //freopen("dfs.in","r",stdin);
    ifstream fin;
    fin.open("dfs.in");
    freopen("dfs.out","w",stdout);
    int nodeCount, edgeCount;
    vector<int>edges[100001];
    fin>>nodeCount>>edgeCount;
    for(int i = 1; i<=edgeCount;i++){
        int node1, node2;
        fin>>node1>>node2;
        edges[node1].push_back(node2);
        edges[node2].push_back(node1);
    }
    queue<int> q;
    int conComponents=0;
    for(int node=1;node<=nodeCount;node++){
        if(visited[node]==0){
            conComponents++;
            q.push(node);
            while (!q.empty()) {
                int thisNode = q.front();
                q.pop();
                if(visited[thisNode] == 1) continue;
                visited[thisNode] = 1;
                for(auto nextNode:edges[thisNode]){
                    q.push(nextNode);
                }
            }
            
        }
    }
    cout<<conComponents;
    return 0;
}