Cod sursa(job #1104803)

Utilizator negrea.andreiAndrei Negrea negrea.andrei Data 11 februarie 2014 00:55:49
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#define N 100005
using namespace std;

struct Node {
	int val;
	Node *next;
};

ifstream f("cycle_detection.in");
ofstream g("cycle_detection.out");

void insert(Node *&top, int val)
{
	Node *newTop = new Node();
	newTop -> next = top;
	newTop -> val = val;

	top = newTop; 
}

void dfs(int s, Node *A[], int* viz)
{
	viz[s] = 1;

	for(Node *it = A[s]; it; it = it -> next)
	{
		if (!viz[it->val])
		{
		  dfs(it->val, A, viz);
		}
	}

}

int main()
{
	int n, m;
	Node *A[N];
	
	f >> n >> m;

	int *viz = new int[n + 5];

	for(int i = 1; i <= n; i++)
	{
		A[i] = 0;
		viz[i] = 0;
	}

	for(int i = 1; i <= m; i++)
	{
		int x, y;
		f >> x >> y;
		insert(A[x], y);
		insert(A[y], x);
	}

	int connected = 0;
	for(int i = 1; i <= n; i++)
	{
		if (!viz[i])
		{
		  dfs(i, A, viz);
		  connected++;
		}
	}

	g << connected;
}