Pagini recente » Cod sursa (job #2835962) | Cod sursa (job #2638077) | Cod sursa (job #2421402) | Cod sursa (job #2310393) | Cod sursa (job #1391174)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const char iname[]="dfs.in";
const char oname[]="dfs.out";
static const int MAXN = 100005;
vector <int> adj[MAXN], viz;
void citeste_in(vector <int> *adj , int &n)
{
int nrMuchii, x, y;
ifstream in(iname);
in>>n>>nrMuchii;
for(; nrMuchii >= 0; nrMuchii--)
{
in>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
in.close();
}
void DFS(int nod, int tata_nod, int nr)
{
vector <int>::iterator it;
viz[nod] = nr;
for(it = adj[nod].begin(); it != adj[nod].end(); ++it)
if(*it != tata_nod)
if(!viz[*it])
DFS(*it, nod, nr+1);
}
int main()
{
int n, cont = 0;
citeste_in(adj, n);
viz.resize(n+1);
viz.assign(n+1, 0);
for(int i = 1; i <= n; i++)
{
if(!viz[i])
{
DFS(i, 0, 0);
cont++;
}
}
ofstream out(oname);
out<<cont;
out.close();
return 0;
}