Pagini recente » Cod sursa (job #2040010) | Cod sursa (job #2388157) | Cod sursa (job #2256191) | Cod sursa (job #2711833) | Cod sursa (job #1458573)
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
void dfs (int x, int n, vector<int>& vis, list<int> adj[])
{
//vector<int> vis[n];
list<int>::iterator it;
vis[x] = 1;
// if (adj[x].empty())
// return;
for (int i = 0; i <= n - 1; i++)
{
it = find(adj[x].begin(), adj[x].end(), i);
if (it != adj[x].end() && !vis[i])
{
//cout<<i<<"aici\n";
dfs (i, n, vis, adj);
}
}
}
int main()
{
int nrConexe = 0;
int m, n, i, x, y;
//list<int> adj;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin >> n;
fin >> m;
list<int> adj[n];
vector<int> vis(n);
//cout<<"CITIRE: \n";
//cout<<m<<" "<<n;
for (i = 0 ; i <= m-1; i++)
{
fin>>x;
fin>>y;
//cout<<x<<" "<<y<<endl;
//cout<<x<<" "<<y<<endl;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (i = 0; i <= n-1 ;i++)
{
// for(int j = 0; j<=n-1;j++)
// cout<<vis[j]<<" ";
// cout<<"\n";
if (!vis[i])
{
//cout<<nrConexe<<" ";
++nrConexe;
//cout<<"IN MAIN!!!!!!!!!!!!\n";
dfs(i, n, vis, adj);
}
}
fout<<nrConexe;
fin.close();
fout.close();
return 0;
}