Cod sursa(job #2382403)

Utilizator Nemo123456nichita Nemo123456 Data 18 martie 2019 11:56:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 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 
 
}