Pagini recente » Cod sursa (job #641283) | Cod sursa (job #418408) | Cod sursa (job #418404) | Cod sursa (job #2065802) | Cod sursa (job #2065800)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int nmax = 100006;
bool viz[nmax];
vector<vector<int> > adj;
void dfs (int root)
{
viz[root] = true;
for(int i = 0;i < (int) adj[root].size();++i)
{
int nod = adj[root][i];
if(!viz[nod])
{
dfs(nod);
}
}
}
int df (int N)
{
int ans = 0;
for(int i = 0;i < N;++i)
{
if(!viz[i])
{
dfs(i);
++ans;
}
}
return ans;
}
int main()
{
int N, M;
ifstream in("dfs.in");
ofstream out("dfs.out");
in >> N >> M;
adj.resize(N);
for(int i = 0;i < M;++i)
{
int a, b;
--a, --b;
adj[a].push_back(b);
adj[b].push_back(a);
}
memset(viz, false, sizeof(viz));
out<< df(N) << "\n";
in.close();
out.close();
}