Cod sursa(job #1705740)

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

using namespace std;

long N, M, nr;

bool visited[100001];

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++) {
		stack<long> S;
		if (!visited[i]){
			S.push(i);
			visited[i] = true;

			while (!S.empty()) {
				long s = S.top();
				S.pop();

				for (unsigned long j = 0; j < adjList[s].size(); j++) {
					if (!visited[adjList[s][j]]) {
						S.push(adjList[s][j]);
						visited[adjList[s][j]] = true;
					}
				}
			}
			nr++;
		}
	}

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

	fclose(input);
	fclose(output);

	return 0;
}