Pagini recente » Cod sursa (job #1104931) | Cod sursa (job #2376872) | Cod sursa (job #1644585) | Cod sursa (job #2571474) | Cod sursa (job #2788619)
#include <iostream>
#include <fstream>
#include<list>
#include<vector>
using namespace std;
void citireGraf(int &N, int &M, vector<list<int> > &L, const char *filename)
{
ifstream fin(filename);
fin >> N >> M;
L.resize(N+1);
int x, y;
for (int i=0;i<M;++i)
{
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
fin.close();
}
void dfs(int nod, vector<list<int>> &L, vector<int> &viz)
{
viz[nod] = 1;
for(int x : L[nod]) // pentru fiecare nod x in lista de vecini
{
if(viz[x] == 0)
{
dfs(x, L, viz);
}
}
}
int main()
{
int N,M;
vector<list<int> > L;
citireGraf(N,M,L,"dfs.in");
vector<int>viz(N+1,0);
int compConexe=0;
for(int i=1;i<=N;++i)
{
if(viz[i]==0){dfs(i, L, viz); compConexe++;}
}
ofstream fout("dfs.out");
fout << compConexe;
fout.close();
return 0;
}