Cod sursa(job #2422942)

Utilizator luizaelenaaaAchim Luiza luizaelenaaa Data 20 mai 2019 14:13:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
//DFS- nr de componente conexe dintr un graf
#include <fstream>
#include <vector>
#define NMAX 100100
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int viz[100100];
vector <int> graf[NMAX];
void DFS(int nod)
{
    viz[nod] = 1;
    //cout<<nod<<" ";
    //cout<<graf[nod].size();
    for(int i=0; i<graf[nod].size(); i++)
    {
        int vecin  = graf[nod][i];
        if(viz[vecin]==0) DFS(vecin);
    }
}
int main()
{
    int n,m,a,b;
    f>>n; //nr noduri;
    f>>m; //nr muchii;
    for(int i=1; i<=m; i++)
    {
        f>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);//graf neorientat
    }
    for(int i=1;i<=n;i++)
        viz[i] = 0;
    int answer = 0;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {//
            answer++;
            DFS(i);
            //cout<<endl;
        }
    }
    //DFS(1);
    //cout<<"graful are "<<answer<<" componente conexe"<<endl;
    g<<answer;
    return 0;
}