Cod sursa(job #846528)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 2 ianuarie 2013 13:10:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int N, M, sol, lu[100100];
bool ap[100100];

vector<int> A[100100];
stack<int> S;

void DFs(int i)
{
	S.push(i);
	ap[i] = true;
	A[i].push_back(0);
	
	while (lu[i] < (int)A[i].size())
	{
		int nod = S.top();
		
		while (lu[nod] < A[nod].size() && ap[A[nod][lu[nod]]]) ++lu[nod];
		
		if (lu[nod] < (int)A[nod].size())
		{
			int var = A[nod][lu[nod]];
			++lu[nod];
			S.push(var);
			ap[var] = true;
		}
		else
		{
			S.pop();
		}
	}
	
	++sol;
}

int main()
{
	fin >> N >> M;
	for (int i = 1; i <= M; ++i)
	{
		int x, y;
		fin >> x >> y;
		A[x].push_back(y);
		A[y].push_back(x);
	}
	
	for (int i = 1; i <= N; ++i)
	{
		if (!ap[i])
		{
			DFs(i);
		}
	}
	
	fout << sol << '\n';
	fout.close();
	return 0;
}