Cod sursa(job #2096743)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 29 decembrie 2017 18:00:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
int viz[200001];
int n;
vector<int>graph[100001];
void dfs(int x) {
	viz[x]=1;
	for(int j=0;j<graph[x].size();j++)
		if(viz[graph[x][j]]==0)
            dfs(graph[x][j]);
}

int main()
{
    FILE *fin, *fout;
    int m,i,a,b,componente_conexe;
    fin=fopen("dfs.in","r");
    fout=fopen("dfs.out","w");
    fscanf(fin,"%d %d\n",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fin,"%d %d\n",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(componente_conexe=0,i=1;i<=n;i++)
        if(viz[i]==0){
            dfs(i);
            componente_conexe++;
        }
    fprintf(fout,"%d\n",componente_conexe);
    fclose(fin);
    fclose(fout);
    return 0;
}