Cod sursa(job #3243878)

Utilizator uncle_sam_007ioan bulik uncle_sam_007 Data 21 septembrie 2024 23:20:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX=1e5+5;
int n,viz[NMAX],cnt;
vector <int>g[NMAX];

void DFS(int node){
    viz[node]=1;
    cnt++;
    vector <int>::iterator it;
    for(it=g[node].begin();it!=g[node].end();++it){
        int j=*it;
        if(!viz[j]){
            DFS(j);
        }
    }
}

int main()
{
    int m,x,y,CNT=0;
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;++i){
        if(!viz[i]){
            DFS(i);
            CNT++;
        }
    }
    fout<<CNT;
    return 0;
}