Cod sursa(job #2275698)
| Utilizator | Data | 3 noiembrie 2018 13:51:30 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 50 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.89 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m;
int a[1001][1001];
int VIZ[1001];
int C[1001];
int cont=0;
int main()
{
fin >> n >> m;
for(int i=1;i<=m;i++){
int x,y;
fin >> x >> y;
a[x][y]=1;
a[y][x]=1;
}
int p=1,u=1;
int x=1;
int v;
for(int j=1;j<=n;j++){
if(VIZ[j]==0){
p=1;
u=1;
cont++;
x=j;
VIZ[x]=cont;
C[1]=x;
while(p<=u){
v=C[p++];
for(int i=1;i<=n;i++){
if(a[v][i]==1 && VIZ[i]==0){
u++;
C[u]=i;
VIZ[i]=cont;
}
}
}
}
}
fout << cont;
}
