Cod sursa(job #2954741)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 15 decembrie 2022 10:54:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll NMAX=2e5+5,buffsize=1<<13;
FILE* fin;
char buff[buffsize];
int buffpos=buffsize;
int read(){
    if(buffpos==buffsize) fread(buff,1,buffsize,fin),buffpos=0;
    int n=0;
    while(buff[buffpos]<'0' || buff[buffpos]>'9'){
        ++buffpos;
        if(buffpos==buffsize) fread(buff,1,buffsize,fin),buffpos=0;
    }
    while(buff[buffpos]>='0' && buff[buffpos]<='9'){
        n=(n<<1)+(n<<3)+(buff[buffpos]^48);
        ++buffpos;
        if(buffpos==buffsize) fread(buff,1,buffsize,fin),buffpos=0;
    }
    return n;
}
typedef long long ll;
vector<ll> edg[NMAX];
bool visited[NMAX];
ll deg[NMAX],processed=0;
void dfs(ll u){
    visited[u]=1;
    for(ll i=0;i<edg[u].size();i++){
        if(!visited[edg[u][i]])
            dfs(edg[u][i]);
    }
}
int main(){
    fin = fopen("dfs.in","r");
    ofstream fout("dfs.out");
    ll n=read(),m=read(),ans=0;
    for(ll i=0;i<m;i++){
        ll u=read(),v=read();
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    for(ll i=1;i<=n;i++)
        if(!visited[i]) dfs(i),ans++;
    fout<<ans;
    return 0;
}