Pagini recente » Cod sursa (job #1366621) | Cod sursa (job #2230319) | Cod sursa (job #2670353) | Cod sursa (job #1040741) | Cod sursa (job #2832571)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
//Restrictii
//1 <= N <= 100 000
//0 <= M <= minim(200 000, N * (N + 1) / 2)
//Pentru 50 % dintre teste 1 <= N <= 1 000
ifstream f("dfs.in");
ofstream g("dfs.out");
vector<int> v[1000001];
int nod_vazut[1000001];
void determina_vecini(int m) {
int x, y;
for (int i = 0; i < m; i++) {
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void DFS(int s)
{
nod_vazut[s] = 1;//notam ca am parcurs nodul de start s
for (int vecin : v[s])
if (!nod_vazut[vecin]) { //daca nodul vecin nu a fost vazut
DFS(vecin);//go deep into it
}
}
void getnrCompConexe(int x)
{
int nr = 0;
for (int i=1; i<=x; i++)
if (nod_vazut[i] == 0)
{
nr++;
DFS(i);
}
g << nr;
}
int main() {
int n, m;
f >> n >> m;
determina_vecini(m);//verificare pentru toate muchiile x,y si viceversa y,x
getnrCompConexe(n);
f.close();
g.close();
return 0;
}