Cod sursa(job #1188289)
Utilizator | Crivat Victor victor_crivat | Data | 19 mai 2014 11:27:07 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream ff("dfs.out");
vector <int> g[100005];
int n,m,i,x,y,nr;
bool del[100005];
void df(int x)
{vector <int> ::iterator it;
del[x]=true;
for (it=g[x].begin();it!=g[x].end();it++)
if (del[*it]==false)
df(*it);
}
int main()
{f>>n>>m;
for (i=1;i<=m;i++)
{f>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for (i=1;i<=n;i++)
if (!del[i]) {df(i);
nr++;}
ff<<nr;
f.close();
ff.close();
return 0;
}