Cod sursa(job #2797177)

Utilizator iulia.chereji21Chereji Iulia iulia.chereji21 Data 9 noiembrie 2021 14:29:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

FILE *fin, *fout;
int N, M, x, y, nrComp;
const int NMAX=100001;
vector <int>graph[NMAX];
bool found[NMAX];

void dfs(){
    stack <int> s;
    nrComp=0;
    int current;
    for(int nod=1;nod<=N;nod++){
        if(found[nod]==false){
            nrComp++;
            s.push(nod);
            found[nod]=true;
            while(!s.empty()){
                current=s.top();
                s.pop();
                found[current]=true;
                for(auto itr: graph[current]){
                    if(found[itr]==false){
                        s.push(itr);
                    }
                }
            }
        }
    }

}

int main()
{
    fin=fopen("dfs.in","r");
    fout=fopen("dfs.out","w");

    fscanf(fin,"%d %d",&N, &M);
    for(int i=0;i<M;i++){
        fscanf(fin,"%d %d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for(int i=1;i<=N;i++){
        found[i]=false;
    }

    dfs();
    fprintf(fout,"%d",nrComp);
    fclose(fin);
    fclose(fout);


    return 0;
}