Cod sursa(job #1035144)

Utilizator TeOOOVoina Teodora TeOOO Data 18 noiembrie 2013 12:44:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
// Include
#include <stdio.h>
#include <vector>
using namespace std;
FILE *in,*out;

//Define
#define pb push_back

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

//Functii
void dfs(int node);

// Variabile
int nodes, edges, from, to;
int visited[sz];
int vodafone; // mindfuck
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--)
	{
		fscanf(in,"%d%d",&from, &to);
		graph[from].pb(to);
		graph[to].pb(from);
	}

	for(int i=1; i<=nodes; ++i)
	{
		if(!visited[i])
		{
			visited[i] = true;
			dfs(i);
			++vodafone;
		}
	}
	fprintf(out, "%d", vodafone);
    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);
		}
	}
}