Cod sursa(job #1085279)

Utilizator TeOOOVoina Teodora TeOOO Data 16 ianuarie 2014 21:36:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
//Include
#include <stdio.h>
#include <vector>
using namespace std;

FILE *in, *out;

//Definitii
#define pb push_back

//Constante
const int sz = (int)1e5+1;

//Functii
void dfs(int node);

//Variabile
int nodes, edges, components;
bool visited[sz];
vector <int> graph[sz];

//Main
int main()
{
	in=fopen("dfs.in", "rt");
	out=fopen("dfs.out", "wt");
    fscanf(in,"%d%d", &nodes, &edges);
    while(edges--)
    {
        int rfrom, rto;
        fscanf(in,"%d%d", &rfrom, &rto);
        graph[rfrom].pb(rto);
        graph[rto].pb(rfrom);
    }

    for(int i=1; i<=nodes; ++i)
    {
        if(!visited[i])
        {
            visited[i] = true;
            dfs(i);
            components++;

        }
    }

    fprintf(out,"%d", components);

	fclose(in);
	fclose(out);
	return 0;
}

void dfs(int node)
{
    vector <int>::iterator it, end = graph[node].end();
    for(it = graph[node].begin(); it!=end; ++it)
        if(!visited[*it])
        {
            visited[*it] = true;
            dfs(*it);
        }
}