Cod sursa(job #1941761)

Utilizator bobotheslayerBogdan Zaharia bobotheslayer Data 27 martie 2017 16:17:44
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100005
using namespace std;
int n,m,marcat[MAX_N];
vector<int> v[MAX_N];

void dfs (int j, int comp)
{
    int t;
    marcat[j]=comp;
    for (t=0; t<v[j].size(); ++t)
    {
        if (v[j][t]!=0 && marcat[t]==0)
        {
            dfs(t,comp);
        }
    }
}

int main()
{
    FILE *intrare,*iesire;
    int i,j,x,y,comp=1;
    intrare=fopen("dfs.in","r");
    iesire=fopen("dfs.out","w");
    fscanf(intrare,"%d%d",&n,&m);
    for (i=0; i<=m-1; ++i)
    {
        fscanf(intrare,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (i=0; i<=n-1; ++i)
    {
        for (j=0; j<v[i].size(); ++j)
        {
            if (v[i][j]!=0 && marcat[j]==0)
            {
                dfs(j,comp);
                ++comp;
            }
        }
    }

    fprintf(iesire,"%d",comp);
    return 0;
}