Cod sursa(job #2357483)

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

using namespace std;

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

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

node *head, *temp, *tail, *Lda[100];

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

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

void dfs(int q)
{
	viz[q]=1;
	//fo << " " << q;
	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]);
	}
	//fo << " Nr noduri=" << n << "\n Nr muchii=" << m;
	
	/*fo << "\n\n Listele de adicenta: \n";
	for(i=1; i<=n; i++)
	{
		temp=Lda[i];
		fo << " Lda[" << i << "] : ";
	 	while(temp)
	 	{
	 		M[i]++;
	 		fo << temp->date << " -> ";	
	 		temp=temp->next;
		}
		fo << "NULL\n";
		
		if(Mx < M[i]) Mx=M[i];
	}*/
	
	/*fo << "\n Grad max=" << Mx;
	fo << "\n Nodurile cu grad max :\n";
	for(i=1; i<=n; i++)
	if (M[i]==Mx) fo << " " << i;*/
	
	//fo << "\n\n Parcurgere in adancime (DFS):\n";
	for(i=1; i<=n; i++)
	{
		if (!viz[i]) 
		{
			dfs(i);
			k++;
			//fo << '\n';
		}
	}
	//fo << '\n';
	
	/*if(k)
	{
		fo << " Graful nu este conex\n Nr componentelor grafului=" << k;
	}
	else fo << " Graful este conex";
	*/
	fo << k;
	
		
}