Cod sursa(job #2075927)
Utilizator | Data | 25 noiembrie 2017 21:04:31 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 55 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.7 kb |
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int vc[100001];
vector<int> g[10001];
void dfs(int node)
{
int a,j;
vc[node]=1;
a=g[node].size();
for(j=0;j<a;j++)
if(vc[g[node][j]]==0)
dfs(g[node][j]);
}
int main()
{
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n,i,a,b,nrsol=0,m;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(i=1;i<=n;i++)
{
if(vc[i]==0){
cout<<"\n";
dfs(i);
nrsol++;
}
}
fout<<nrsol;
return 0;
}