Cod sursa(job #1705745)

Utilizator RaresvisRares Visalom Mihail Raresvis Data 20 mai 2016 22:47:11
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

long N, M, nr;

bool visited[100001];

void DFS(const vector< vector<long> > &adjList, int node) {
	visited[node] = true;

	for (unsigned long i = 0; i < adjList[node].size(); i++) {
		if (!visited[adjList[node][i]]) {
			DFS(adjList, adjList[node][i]);
		}
	}
}

int main () {
	FILE* input = fopen("dfs.in", "r");
	FILE* output = fopen("dfs.out", "w");

	fscanf(input, "%ld %ld", &N, &M);

	vector< vector<long> > adjList(N+1, vector<long>());

	long u, v;
	for (long i = 0; i < M; i++) {
		fscanf(input, "%ld %ld", &u, &v);

		adjList[u].push_back(v);
	}

	for (long i = 1; i <= N; i++) {
		if (!visited[i]){
			DFS(adjList, i);
			nr++;
		}
	}

	fprintf(output, "%ld", nr);

	fclose(input);
	fclose(output);

	return 0;
}