Pagini recente » Cod sursa (job #187482) | Cod sursa (job #46211) | Cod sursa (job #1342302) | Cod sursa (job #1637202) | Cod sursa (job #2926629)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int noduri,muchii,i;
int nr;
vector< int > vizitate(100001,0);
int compConexe[100001]={0};
vector< vector<int> > ListaAdiacenta()
{ int x,y;
vector< vector<int> > lista(noduri+1);
for( i=0;i<muchii;i++)
{
f>>x>>y;
lista[x].push_back(y);
lista[y].push_back(x);
}
return lista;
}
//void afisareListaAdiacenta(vector<vector<int>> &lista)
//{
// for(size_t x=1; x< lista.size();x++)
// {
// cout<<x<<": ";
// for(auto y:lista[x])
// cout<<y<<" , ";
// cout<<endl;
// }
// cout<<endl;
//}
void DFS(int nod,vector< vector<int> > &lista,int componenteConexe[10001])
{
vizitate[nod]=1;
componenteConexe[nod]=nr;
// for(int i = 0; i < lista[nod].size(); i++)
// if(!vizitate[lista[nod][i]])
// DFS(lista[nod][i],lista,componenteConexe);
for(auto y:lista[nod])
if(!vizitate[y])
DFS(y,lista,componenteConexe);
}
int gasesteCompConexe(vector< vector<int> > &lista,int N,int componenteConexe[10001])
{
for(int i=1;i<=N;i++)
if(!vizitate[i])
{
nr++;
DFS(i,lista,componenteConexe);
}
return nr;
}
int main()
{
f>>noduri>>muchii;
auto listaAdiacenta= ListaAdiacenta();
// afisareListaAdiacenta(listaAdiacenta);
g<<gasesteCompConexe(listaAdiacenta,noduri,compConexe);
return 0;
}