Pagini recente » Cod sursa (job #617794) | Cod sursa (job #2081976) | Cod sursa (job #2838260) | Cod sursa (job #496523) | Cod sursa (job #1825457)
#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("dfs.in", ios::in);
fstream f2("dfs.out", ios::out);
///ai un graf neorientat cu n noduri si m muchii
///sa se det numarul de componente conexe ale grafului
///poti afla asta facand dfs-uri succesive pentru nodurile nevizitate
int32_t n, m, v[200001], cap[100001], viz[100001], pas[100001], nrcomp;
struct muchie
{
int x, y;
}mu[200001];
void dfs(int32_t i)
{
///varianta recursiva
viz[i]=1;
///vizitezi nodul curent
///alegi primul fiu nevizitat, apoi primul fiu al primului fiu nevizitat
///ma intorc recursiv cand intr-un nod nu mai am fii nevizitati
///la iesire din functie vizitezi toate nodurile unei componente conexe
int32_t j;
for(j=cap[i]; j<cap[i+1]; j++)
if(!viz[v[j]]) dfs(v[j]);
}
int main()
{
int32_t i, x, y;
f1>>n>>m;
for(i=1; i<=m; i++)
{
f1>>x>>y;
mu[i].x=x;
mu[i].y=y;
///pas[i] memo provizoriu numarul de fii ai lui i
pas[x]++;
pas[y]++;
}
cap[1]=1;
for(i=1; i<=n; i++)
{
cap[i+1]=cap[i]+pas[i];
pas[i]=cap[i];
}
pas[1]=1;
for(i=1; i<=m; i++)
{
x=mu[i].x;
y=mu[i].y;
v[pas[x]]=y;
pas[x]++;
v[pas[y]]=x;
pas[y]++;
}
///ai creat lista de adiacenta
///faci dfs-ul
for(i=1; i<=n; i++)
if(!viz[i]) {nrcomp++;dfs(i);}///faci cate o parcurgere de la capat pt fiecare nod neviz
f2<<nrcomp;
return 0;
}