Cod sursa(job #1481549)

Utilizator dimavascan94VascanDumitru dimavascan94 Data 4 septembrie 2015 19:11:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <stack>
using namespace std;

#define MAX 100005

int n, m, nrCompCon = 1, i, a, b, conn[MAX], current, adListSize,lastVisited;
vector<int> graph[MAX];
stack<int> mySt;


int main()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%d%d", &n, &m);
	memset(conn, -1, (n+1)*4);

	for (i = 0; i < m; ++i)	scanf("%d%d", &a, &b), graph[a].push_back(b), graph[b].push_back(a);
	mySt.push(1);
	lastVisited = 1;
	conn[1] = 1;

	while (mySt.size()>0 || lastVisited <= n)
	{
		if (mySt.size()>0)	current = mySt.top(),mySt.pop();
		else 
		{
			while (++lastVisited <= n)
			{
				if (conn[lastVisited] == -1) current = lastVisited;
				break;
			}
			if (lastVisited > n)	break;
		}
		adListSize = graph[current].size();

		if (conn[current] == -1) conn[current] = ++nrCompCon;

		adListSize = graph[current].size();
		for (i = 0; i < adListSize; ++i)
			if (conn[graph[current][i]]==-1)	conn[graph[current][i]] = conn[current],mySt.push(graph[current][i]);
	}

	printf("%d", nrCompCon);

}