Cod sursa(job #2455575)

Utilizator sebastianlazarLazar Constantin Sebastian sebastianlazar Data 11 septembrie 2019 22:40:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>
#define nmax 100010
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int>A[nmax];
int Cost[nmax],G[nmax], S[nmax], nod1,nod2, ccon, n, m;
int i, j;
void dfs(int nod);
int main()
{
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> nod1 >> nod2;
		A[nod1].push_back(nod2);
		A[nod2].push_back(nod1);
		G[nod1]++;
		G[nod2]++;
	}
	for (i = 1; i <= n; i++)
	{
		if (Cost[i] == 0)
		{
			ccon++;
			Cost[i] = ccon;
			dfs(i);
		}
	}
	fout << ccon;
	return 0;
}
void dfs(int nod)
{
	int L,i1;
	L = 1;
	S[L] = nod;
	for(i1=1;i1<=L;i1++)
	{ 
	for (j = 0; j < G[S[i1]]; j++)
	{
		if (Cost[A[S[i1]][j]] == 0)
		{
			S[++L] = A[S[i1]][j];
			Cost[S[L]] = Cost[S[i1]];
		}
	}
	}
}