Cod sursa(job #1832318)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 19 decembrie 2016 19:47:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>

using namespace std;
vector <int> l[100001];
int c[100001],f[100001];
void bfs (int i){
    int p,u,j;
    p=u=1;
    c[p]=i;
    f[c[p]]=1;
    while (p<=u){
        for (j=0;j<l[c[p]].size();j++){
            if (f[l[c[p]][j]]==0){
                f[l[c[p]][j]]=1;
                c[++u]=l[c[p]][j];
            }
        }
        p++;
    }
}
int main()
{
    FILE *fin=fopen ("dfs.in","r");
    FILE *fout=fopen ("dfs.out","w");
    int n,m,a,b,conex,i;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&a,&b);
        l[a].push_back(b);
        l[b].push_back(a);
    }
    conex=0;
    for (i=1;i<=n;i++){
        if (f[i]==0){
            conex++;
            bfs(i);
        }
    }
    fprintf (fout,"%d",conex);
    return 0;
}