Cod sursa(job #2202581)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 9 mai 2018 11:15:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
#define N 100001
int a[2*N];
int b[2*N];
int c[N];
bool v[N];
int k;
void DFS(int i){
    v[i]=1;
    i=c[i];
    while(i){
        if(!v[a[i]])
            DFS(a[i]);
        i=b[i];
    }
}
void add(int x, int y){
    a[++k]=y;
    b[k]=c[x];
    c[x]=k;
}
int main(){
    int n,m,i,j,x,y;
    in>>n>>m;
    for(i=1; i<=m; ++i){
        in>>x>>y;
        add(x,y);
        add(y,x);
    }
    int s=0;
    for(i=1; i<=n; ++i){
        if(!v[i]){
            DFS(i);
            ++s;
        }
    }
    out<<s;
    return 0;
}