Pagini recente » Cod sursa (job #1962884) | Cod sursa (job #1996721) | Cod sursa (job #2426440) | Cod sursa (job #738843) | Cod sursa (job #3254543)
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, nrc;
vector <int> A[NMAX];
///a[ x] va fi un vec din stl care retie lista de adacenta a lui x
///d[x] gradul lui x/grd exterior
int viz[NMAX]; /// viz[x] = nr daca a fost vizitat in comp conexa cu num nr
void citire();
void dfs(int x);
void afisare();
int main()
{
///graf rep prin liste de adiacenta tipul vector din biblioteca stl
citire();
int i;
for(i = 1 ; i <= n; i++)
if(!viz[i])
{
nrc ++;
dfs(i);
}
afisare();
return 0;
}
void citire()
{
int i, x, y;
fin >> n;
while(fin >> x >> y)
{
///varful y e adaugat la lista de adiacenta a lui x
A[x].push_back(y);
/// varful x e adaugat la lista de adiacenta a lui x
A[y].push_back(x);
}
}
void dfs(int x)
{
int i;
viz[x] = nrc;
///parcurg vecinii varfului x sau adiacente
for(i = 0; i < A[x].size(); i++)
if(!viz[A[x][i]])
dfs(A[x][i]);
}
void afisare()
{
fout << nrc << '\n';
/*int i, j;
for(i = 1; i <= nrc; i++)
{
for(j = 1; j <= n; j ++)
if(viz[j] == i)
fout << j << ' ';
fout << '\n';
}*/
}