Cod sursa(job #1466803)
Utilizator | Mihai Musat mihaimusat | Data | 30 iulie 2015 16:08:50 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 15 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.63 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
#define NMAX 100005
vector<int> g[NMAX];
int viz[NMAX];
int n,m,i,a,b,nr;
void dfs(int x)
{
viz[x] = 1;
for(i=0;i<g[x].size();i++)
{
if(viz[g[x][i]]==0) {
dfs(g[x][i]);
}
}
}
int main()
{
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(i=1;i<=n;i++)
{
if(viz[i]==0) {
nr++;
dfs(i);
}
}
cout<<nr;
return 0;
}