Pagini recente » Cod sursa (job #479247) | Cod sursa (job #989561) | Cod sursa (job #1410209) | Cod sursa (job #734180) | Cod sursa (job #1825454)
#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], stiva[100001], vf=1, pas[100001], nrcomp;
struct muchie
{
int x, y;
}mu[200001];
void dfs()
{
///varianta iterativa
int32_t i;///i =indice care se plimba prin v
///cauti primul fiu al lui x, apoi primul fiu al fiului ales al lui x...
while(vf!=0)
{
i=cap[stiva[vf]];
while((i<cap[stiva[vf]+1])&&(viz[v[i]])) i++;///incerci sa gasesti primul fiu nevizitat
if(i==(cap[stiva[vf]+1])) vf--;///daca nu ai gasit niciun fiu te intorci recursiv
else
{
vf++;
stiva[vf]=v[i];
viz[v[i]]=nrcomp;
}
}
}
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++;vf=1;stiva[vf]=i;viz[i]=nrcomp;dfs();}///faci cate o parcurgere de la capat pt fiecare nod neviz
f2<<nrcomp;
return 0;
}