Cod sursa(job #833312)

Utilizator maritimCristian Lambru maritim Data 12 decembrie 2012 11:43:28
Problema Parcurgere DFS - componente conexe Scor 35
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");
FILE *g = fopen("dfs.out","w");

typedef vector<int>::iterator it;

#define MaxN 100100

int N,M,Sol;
vector<int> A[MaxN];
int viz[MaxN];

void citire(void)
{
    int a,b;

    fscanf(f,"%d %d\n",&N,&M);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%d %d",&a,&b);
        A[a].push_back(b);
        A[b].push_back(a);
    }
}

inline void DFS(int a)
{
    viz[a] = 1;
    for(it i=A[a].begin();i<A[a].end();i++)
        if(!viz[*i])
            DFS(*i);
}

void Rezolvare(void)
{
    for(int i=1;i<=N;i++)
        if(!viz[i])
            DFS(i),++Sol;
}

int main()
{
    citire();
    Rezolvare();

    fprintf(g,"%d\n",Sol);
}