Cod sursa(job #1345598)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 17 februarie 2015 19:07:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <vector>

using namespace std;

class LinkedList
{
public:

	int info;
	LinkedList *next, *prev;

	LinkedList()
	{
		next = NULL;
		prev = NULL;
	}

	LinkedList(int info)
	{
		next = NULL;
		prev = NULL;
		this->info = info;
	}

	void addElement(int info)
	{
		LinkedList * aux = new LinkedList(info);
		aux->next = next;
		aux->prev = this;
		next = aux;
	}

	void deleteNext()
	{
		if(next == NULL)
			return;
		next->next->prev = this;
		next = next->next;
	}

};

class Stack
{
public:
	LinkedList top;

	void push(int element)
	{
		if(top.next!=NULL)
		{
			top.next->prev = new LinkedList(element);
			top.next->prev->next = top.next;
			top.next->prev->prev = &top;
			top.next = top.next->prev;
			return;
		}
		top.next = new LinkedList(element);
		top.next->prev = &top;
	}

	int pop()
	{
		int aux = top.next->info;
		top.next = top.next->next;
		if(top.next!=NULL)
			top.next->prev = &top;
		return aux;
	}

	bool isEmpty()
	{
		return top.next == NULL;
	}

	int peek()
	{
		return top.next->info;
	}
};

vector<int>edges[100002];
int visited[100002];

void visit (Stack s, int nr)
{
	while(s.isEmpty()==false)
	{
		int current = s.pop();
		for(int i=0; i<edges[current].size(); ++i)
			if(visited[edges[current][i]]==0)
			{
				visited[edges[current][i]] = nr;
				s.push(edges[current][i]);
			}
	}
}

int main()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	int n, m, i, j;
	scanf("%d%d", &n, &m);

	for(i=1; i<=m; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		edges[y].push_back(x);
		edges[x].push_back(y);
	}

	j=1;
	for(i=1; i<=n; ++i)
		if(visited[i]==0)
		{
			Stack s;
			s.push(i);
			visited[i] = j;
			visit(s, j);
			++j;
		}

	printf("%d\n", j-1);
	return 0;
}