Cod sursa(job #2346069)

Utilizator Nemo123456nichita Nemo123456 Data 17 februarie 2019 00:40:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

int viz[100001],n,m,x,y,p;

typedef struct celula{
	int nr;
	celula *next;
} *pcelula;
pcelula a[100001];

void add(celula* &node , int val )
{
	pcelula r;
	r = new celula;
	r->nr = val;
	r->next=node;
	node = r;
}

void citire()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		{
			cin>>x>>y;
			add(a[x],y);
			add(a[y],x);
		}
	
}
/*
void af()
{
	for(int i=1;i<=n;i++)
			{
				r=a[i];
				while(r!=NULL)
					{
						cout<<r->nr<<' ';
						r=r->next;
					}
				cout<<endl;
			}
}
*/
void dfs(int nod)
{
	pcelula r;
	viz[nod]=1;
	for(r = a[nod];r!=NULL;r=r->next) if(!viz[r->nr]) dfs(r->nr);
}

void doit()
{
	for(int i=1;i<=n;i++) if(!viz[i]) {p++;dfs(i);}
	cout<<p;
}

int main()
{
	citire();
	doit();		

// 1 

}