Cod sursa(job #2767843)

Utilizator un_fes_galbendaniel guba un_fes_galben Data 7 august 2021 23:48:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
char buff[4096];
int pbuf=4095;
void readbuff()
{
    pbuf=0;
    fin.read(buff,4095);
}
int citire()
{
    int nr=0;
    if(pbuf==4095)
    {
        readbuff();
    }
    while(buff[pbuf]<'0'||buff[pbuf]>'9')
    {
        pbuf++;
        if(pbuf==4095)
        {
            readbuff();
        }
    }
    while(buff[pbuf]>='0'&&buff[pbuf]<='9')
    {
        nr=nr*10+buff[pbuf]-'0';
        pbuf++;
        if(pbuf==4095)
        {
            readbuff();
        }
    }
    return nr;
}
vector<int>adiacent[100005];
int viz[100005];
void DFS(int x){
     for(auto i:adiacent[x]){
        if(viz[i]==0){
            viz[i]=1;DFS(i);
        }
     }
}
int main()
{
    int n,m,a,b,cnt=0;
    n=citire();m=citire();
    for(int i=1;i<=m;i++){
        a=citire();
        b=citire();
        adiacent[a].push_back(b);
        adiacent[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(viz[i]==0){
            viz[i]=1;cnt++;
            DFS(i);
        }
    }
    fout<<cnt<<'\n';
    return 0;
}