Cod sursa(job #891969)

Utilizator AliqhuartZotica Alexandru Corin Aliqhuart Data 25 februarie 2013 21:28:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<stdio.h>
#include<vector>
using namespace std;
vector<long> vec[100001];
long m,n,raspuns;
long v[100001];
void dfs(long nod)
{
    v[nod]=1;
    for(long i=0;i<vec[nod].size();i++)
        if(v[vec[nod][i]]==0)
            dfs(vec[nod][i]);
}
int main()
{
    FILE *f;
    FILE *g;
    f=fopen("dfs.in","rt");
    g=fopen("dfs.out", "wt");
    fscanf(f,"%d %d", &n, &m);
    for(long i=1;i<=m;i++)
    {long x,y;
     fscanf(f,"%d %d", &x, &y);
     vec[x].push_back(y);
     vec[y].push_back(x);
    } 
    for(long i=1;i<=n;i++)
        if(v[i]==0)
        {
            dfs(i);
            raspuns++;
        }
    fprintf(g,"%d", raspuns);
    fclose(f);
    fclose(g);
    return 0;
}