Pagini recente » Cod sursa (job #1667199) | Cod sursa (job #2946480) | Cod sursa (job #2484195) | Cod sursa (job #1519655) | Cod sursa (job #2787315)
#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
class graf{
public:
//bfs - declarari
//int N, M, S, vizitat[100010], minime[100010];
//vector<int> stocare[100010];
//queue<pair<int, int>> coada;
//dfs - declarari
int N, M;
vector<int>ok; //pt a marca nodul ca vizitat sau nu - 0 sau 1
vector<vector<int>>D;
graf(){}
//DFS
void dfs(int start)
{
ok[start] = 1;
for(auto i: D[start]) // parcurg D
if(!ok[i])
{
ok[i] =1;
dfs(i);
}
}
void creare_graf_Dfs(int N, int M)
{
this-> N = N;
this -> M =M;
D=vector<vector<int>>(N+1);
ok=vector<int>(N+1);
}
void creare_adiacente_Dfs(int M)
{
int nod1, nod2;
for(int i = 1; i<= M; i++)
{
f>>nod1>>nod2;
D[nod1].push_back(nod2);
D[nod2].push_back(nod2);
}
}
};
graf Gr;
int main()
{
//DFS
int N, M, k;
f>>N>>M;
Gr.creare_graf_Dfs(N, M);
Gr.creare_adiacente_Dfs(M);
for(int i =1; i<= N; i++)
if(!Gr.ok[i])
{
k++;
Gr.dfs(i);
}
g<<k<<" ";
return 0;
}