Cod sursa(job #2476104)

Utilizator Leonard123Mirt Leonard Leonard123 Data 18 octombrie 2019 09:04:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
#include<vector>
using namespace std;
#define maxn 100005
vector<int> nod[maxn];
ifstream cin ("dfs.in");
ofstream cout ("dfs.out");
int verificat[maxn],nr[maxn],n,m,cnt;

void dfs(int i){
  verificat[i]=1;
    for(int j=0; j<nr[i]; j++)
        if(verificat[nod[i][j]]==0){
            dfs(nod[i][j]);
        }
}

void solve(){
    for(int i=1; i<=n; i++){
        if(verificat[i]==0){
            cnt++;
            dfs(i);
        }
    }
}

int main(){
    cin>>n>>m;
    int x,y;
    for(int i=1; i<=m; i++){
        cin>>x>>y;
        nod[x].push_back(y);
        nod[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        nr[i]=nod[i].size();
    solve();
    cout<<cnt;
    return 0;
}