Pagini recente » Cod sursa (job #3126623) | Cod sursa (job #2766214) | Cod sursa (job #583179) | Cod sursa (job #1156125) | Cod sursa (job #1202239)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m;
vector<int> G[100005];
bool visited[100005];
void read();
int getNumberOfConexComponents();
void DFS(int nod);
int main()
{
read();
fout<<getNumberOfConexComponents();
return 0;
}
void read()
{
int a,b;
fin>>n>>m;
for(int i=0;i<m;i++)
{
fin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
}
int getNumberOfConexComponents()
{
int result = 0;
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++)
{
if(!visited[i])
{
result++;
DFS(i);
}
}
return result;
}
void DFS(int nod)
{
visited[nod] = true;
for(unsigned int i=0;i<G[nod].size();i++)
{
if(!visited[G[nod][i]])
{
DFS(G[nod][i]);
}
}
}