Cod sursa(job #2357489)

Utilizator Hey_HeyIacovlev Denis Hey_Hey Data 27 februarie 2019 14:30:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>

using namespace std;

ifstream fi("dfs.in");
ofstream fo("dfs.out");

typedef struct 
	node
	{
		int date;
		node *next;	
	}*list;

list head, temp, tail, Lda[100005];

int n, m, Mx, x, y, i, k;
bool viz[100005];

void add(int q, node *&head)
{
	list temp=new node;
	temp->date=q;
	temp->next=head;
	head=temp;
}

void dfs(int q)
{
	viz[q]=1;
	for(node *head=Lda[q]; head; head=head->next) 
	if (!viz[head->date]) dfs(head->date);
}

int main()
{
	fi >> n >> m;
	
	for(i=1; i<=n; i++) Lda[i]=NULL;
	
	for(i=1; i<=m; i++)
	{
		fi >> x >> y;
		add(y,Lda[x]);
		add(x,Lda[y]);
	}
	
	for(i=1; i<=n; i++)
	{
		if (!viz[i]) 
		{
			dfs(i);
			k++;
			
		}
	}
	fo << k;
	
		
}