Cod sursa(job #2377311)

Utilizator munteanue28no one munteanue28 Data 9 martie 2019 17:09:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;

	ifstream fi ("dfs.in");
	ofstream fo ("dfs.out");
	
	typedef struct nod {
		int info;
		nod *next;
	} *lista;
	
	int i,j,n,m,x,y, p=0;
	bool viz[200001];
	lista A[200001];
	
	void add (lista &p, int k)
	{
		lista r = new nod;
		r->info = k;
		r->next = p;
		p=r;
	}
	
	void dfs ( int x)
	{
		viz[x]=1; 
		for (lista p=A[x]; p; p=p->next)
			if (viz[p->info] == 0) dfs (p->info);
	}
	
	int main () {
			
		fi >>n>>m ; 
		
		while (m--)
		{
			fi>>x>>y;
			add	(A[y],x);
			add (A[x],y);
		}

	
	for (i=1; i<=n; i++)
	{
		if (viz[i] == 0) 
		{
			dfs(i);
			p++;
		}
	}
	
	fo<<p;
	
	return 0;
	
}