Cod sursa(job #870755)

Utilizator TeOOOVoina Teodora TeOOO Data 3 februarie 2013 21:30:38
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <vector>
using namespace std;

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

//Functii
void dfs(int node);

//Variabile
FILE *in,*out;

int nodes, edges;
int answer;
bool visited[sz];

vector<int> graph[sz];

int main()
{
  in=fopen("dfs.in","rt");
  out=fopen("dfs.out","wt");
  fscanf(in, "%d%d",&nodes, &edges);
	while(edges--)
	{
	    int vFrom, vTo;
		fscanf(in, "%d%d",&vFrom, &vTo);
		graph[vFrom].push_back(vTo);
	}
    for(int i=1; i<=nodes; ++i)
        if(!visited[i])
        {
            dfs(i);
            ++answer;
        }
    fprintf(out,"%d",answer);

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

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