Cod sursa(job #3276549)

Utilizator cosmin_maMurariu Cosmin cosmin_ma Data 13 februarie 2025 20:30:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m, viz[100001], k;

struct nod {
	int vf;
	nod* urm;
}*v[100001];


void adaugare(int x,nod*& prim)
{
	nod* nou = new nod;
	nou->vf = x;
	nou->urm = prim;
	prim = nou;
}

void citire()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fin >> x >> y;
		adaugare(x, v[y]);
		adaugare(y, v[x]);
	}
}


void dfs(int x)
{
	viz[x] = k;
	for (nod*q=v[x];q;q=q->urm)
	{
		if (!viz[q->vf])
		{
			dfs(q->vf);
		}
	}
}

int main()
{
	citire();
	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
		{
			k++;
			dfs(i);
		}
	}
	fout << k;
}