Pagini recente » Monitorul de evaluare | Cod sursa (job #1477942) | Cod sursa (job #380726) | Cod sursa (job #2582259) | Cod sursa (job #2424466)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
void DFS(int node, vector<vector<int>> &g, vector<int> &eticheta, int comp)
{
eticheta[node]=comp;
for(auto vecin : g[node]) ///for(i=0;i<g[node].size();i++) int vecin = g[node][1];
{
if(eticheta[vecin]==0)
DFS(vecin, g, eticheta, comp);
}
}
int main()
{
int n, m;
in>>n;
in>>m;
vector<vector<int>> g(n);
for(int i=0;i<m;i++)
{
int a, b;
in>>a;
in>>b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> eticheta(n,0);
int comp = 1;
for(int i=0;i<n;i++)
{
if(eticheta[i]==0)
DFS(i,g,eticheta,comp);
comp++;
}
int nr = 0;
for(int i=0;i<n;i++)
{
if(eticheta[i] == 0)
nr++;
}
out << nr;
return 0;
}