Pagini recente » Cod sursa (job #1208675) | Cod sursa (job #326029) | Cod sursa (job #8547) | Cod sursa (job #1378979) | Cod sursa (job #2788643)
#include <iostream>
#include <fstream>
#include<list>
#include<vector>
#include<queue>
using namespace std;
int tata[100];
void citireGraf(int &N, int &M, vector<list<int> > &L, const char *filename)
{
ifstream fin(filename);
int x,y;
fin >> N >> M;
L.resize(N+1);
for (int i=1; i<=M; i++)
{
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
fin.close();
}
void afisare(vector<list<int> > &L)
{
for(int i = 1; i<L.size();i++)
{
cout << i << ":";
for(int j:L[i])
cout << j << " ";
cout << "\n";
}
}
void dfs(int nod, vector<list<int>> &L, vector<int> &viz)
{
viz[nod] = 1;
for(int i : L[nod])
{
if(viz[i] == 0)
{
tata[i] = nod;
dfs(i,L,viz);
}
}
}
int main()
{
int N,M,c;
vector<list<int> > L;
citireGraf(N,M,L,"dfs.in");
vector<int>viz(N+1,0);
// afisare(L);
int noCompConexe=0;
for(int i = 1; i <= N; ++i)
{
if(viz[i] == 0)
{dfs(i,L,viz);
noCompConexe ++;}
}
ofstream fout("dfs.out");
fout<<noCompConexe;
fout.close();
return 0;
}