Cod sursa(job #1727852)
| Utilizator | Data | 11 iulie 2016 19:26:52 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.58 kb |
#include <fstream>
#define NMAX 100001
using namespace std;
int freq[NMAX]={0};
void DFS(int *a[],int n,int current){
freq[current] = 1;
for(int i=1;i<=n;i++)
if(a[current][i] && freq[i])
DFS(a,n,i);
}
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,m1,m2,a[NMAX][NMAX];
f >> n >> m;
for(int i=0;i<m;i++){
f >> m1 >> m2;
a[m1][m2] = a[m2][m1] = 1;
}
int c=0;
for(int i=1;i<=n;i++){
c++;
if(!freq[i]) DFS(a,n,i);
}
g << c;
return 0;
}
