Pagini recente » Cod sursa (job #488031) | Cod sursa (job #858353) | Cod sursa (job #2486228) | Cod sursa (job #798175) | Cod sursa (job #2952652)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m;
vector <int> v[NMAX];
void unif()
{
for(int i=1; i<=n; i++)
{
sort(v[i].begin(), v[i].end());
v[i].resize(distance(v[i].begin(),unique(v[i].begin(), v[i].end())));
}
}
int viz[NMAX];
void dfs(int x, int k)
{
viz[x]=k;
for(auto& j:v[x])
{
if(!viz[j]) dfs(j, k);
}
}
int main()
{
fin>>n>>m;
for(int i=1; i<=m; i++)
{
int a, b;
fin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
unif();
int k=1;
for(int i=1; i<=n; i++)
{
if(!viz[i])
{
dfs(i, k);
k++;
}
}
fout<<k-1;
}