Cod sursa(job #1402499)

Utilizator karlaKarla Maria karla Data 26 martie 2015 17:04:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#include <vector>

using namespace std;

FILE*f=fopen("dfs.in","r"),*g=fopen("dfs.out","w");
int n,m,v[100100], nr;
vector<int> L[100100];


void dfs(int nod)
{
    int x;
    v[nod] = 1;
    for(int i = 0; i < L[nod].size(); i++ )
    {
        x = L[nod][i];
        if(v[x] == 0)
            dfs(x);
    }
}

int main()
{
    fscanf(f,"%d %d",&n,&m);
    int x, y;
    for(int i = 1; i <= m; i++)
    {
        fscanf(f,"%d %d\n",&x,&y);
        L[x].push_back(y);
        L[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
    {
        if(v[i] == 0)
        {
            dfs(i);
            nr++;
        }
    }
    fprintf(g,"%d",nr);
    return 0;
}