Pagini recente » Cod sursa (job #679925) | Cod sursa (job #2100129) | Cod sursa (job #1233076) | Cod sursa (job #250087) | Cod sursa (job #2796769)
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
class Graf
{
int nr_N, nr_M;
vector<int> vecini[100001];
public:
/// Constructori
Graf() : nr_N(0), nr_M(0) {}
Graf(int N, int M) : nr_N(N), nr_M(M) {}
void citire();
void DFS(int,vector<int>&);
void conexe();
};
void Graf::citire()
{
in >> nr_N >> nr_M;
for (int i = 0; i < nr_M; i++)
{
int x, y;
in >> x >> y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
}
void Graf::DFS(int S, vector<int>& vizitat)
{
vizitat[S] = 1;
cout << S << " ";
for(int i = 0; i < vecini[S].size(); i++)
{
if (vizitat[vecini[S][i]] ==0)
{
///cout << vecini[S][i] << " ";
DFS(vecini[S][i], vizitat);
}
}
}
void Graf::conexe()
{
vector<int> vizitat;
int nr=0, i;
for(i = 0; i <= nr_N; i++)
vizitat.push_back(0);
for(i = 1; i <= nr_N; i++)
{
if (vizitat[i] == 0)
{
DFS(i,vizitat);
nr++;
}
}
out << nr;
}
int main()
{
Graf G;
G.citire();
G.conexe();
return 0;
}