Cod sursa(job #1217122)
| Utilizator | Data | 6 august 2014 17:11:47 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 15 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.66 kb |
#include<fstream>
#include<vector>
#include<list>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int i,n,m,a,b,con,vizitat[100010];
vector<list<int> > v(100010);
void conex(int nod)
{
list <int> :: iterator it;
vizitat[nod]=con;
for(it=v[nod].begin();it!=v[nod].end();it++)
{
if(vizitat[*it]==0)
conex(*it);
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>a>>b;
v[a].push_back(b);
}
for(i=1;i<=n;++i)
{
if(vizitat[i]==0)
{
con++;
conex(i);
}
}
fout<<con;
return 0;
}
