Cod sursa(job #894245)

Utilizator alin_iliciAlin Ilici alin_ilici Data 26 februarie 2013 20:22:39
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define maxn 100001
vector <int> vec[maxn];
int sel[maxn];

void DFS(int nod)
{
    unsigned int i;
    sel[nod]=1;
    for (i=0;i<vec[nod].size();i++)
    {
        if (sel[vec[nod][i]]==0)
        {
            DFS (vec[nod][i]);
        }
    }
}

int main()
{
    int a,b,n,m,i,nr=0;
    FILE *f,*g;
    f=fopen ("dfsin.txt", "rt");
    g=fopen ("dfsout.txt", "wt");
    fscanf (f,"%d %d", &n, &m);
    for (i=1;i<=m;i++)
    {
        fscanf (f,"%d %d", &a, &b);
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    for (i=1;i<=n;i++)
    {
        sel[i]=0;
    }
    for (i=1;i<=n;i++)
    {
        if (sel[i]==0)
        {
            DFS(i);
            nr++;
        }
    }

    fprintf (g, "%d", nr);
    fclose(f);
    fclose(g);
    return 0;
}