Cod sursa(job #2574785)

Utilizator victor1306Victor Mihaila victor1306 Data 6 martie 2020 09:55:14
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>

using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int vf[400005], urm [400005], lst[100005], nr;
bool viz[200005];
void adauga(int x, int y){
    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}
void dfs(int x){
    viz[x]=true;
    for(int p=lst[x]; p!=0; p=urm[p]){
        int y=vf[p];
        if(viz[y]==0){
            dfs(y);
        }
    }
}
int main()
{
    int n,m,x,y,ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }
    for(int i=1;i<=n;i++){
        if(viz[i]==0){
            dfs(i);
            ans++;
        }
    }
    cout<<ans;
    return 0;
}