Cod sursa(job #3334811)

Utilizator MarusCiobanu Marius Marus Data 20 ianuarie 2026 00:29:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

vector<int> adj[1000001];
int viz[1000001];

void DFS(int start) {
    stack<int> st;
    st.push(start);
    viz[start]=1;

    while (st.size()>0) {
        int nod=st.top();
        st.pop();
        for (int vecin:adj[nod]) {
            if (viz[vecin]==0) {
                st.push(vecin);
                viz[vecin]=1;
            }
        }

    }


}

int main() {

    ifstream fin("dfs.in");
    int N,M,x,y;
    fin>>N>>M;

    for (int i=1;i<=N;i++) {
        adj[i].clear();
        viz[i]=0;
    }

    for (int i=1;i<=M;i++) {
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    int cc=0;

    for (int i=1;i<=N;i++) {
        if (viz[i]==0) {
            DFS(i);
            cc+=1;
        }
    }

    ofstream fout("dfs.out");
    fout<<cc;


}