Mai intai trebuie sa te autentifici.
Cod sursa(job #2195197)
| Utilizator | Data | 15 aprilie 2018 16:31:37 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 10 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.82 kb |
#include <iostream>
#include <stdio.h>
using namespace std;
FILE *f,*g;
int v[100002],a[2][100002],fr[100002];
int m,n;
void citire()
{
int k=0,i,j;
fscanf(f, "%d %d", &n, &m);
for(int l=1; l<=m; l++)
{
fscanf(f, "%d %d", &i, &j);
++k;
a[0][k]=j;
a[1][k]=v[i];
v[i]=k;
++k;
a[0][k]=i;
a[1][k]=v[j];
v[j]=k;
}
}
void dfs(int nod)
{ int ok;
fr[nod]=1;
ok=v[nod];
fr[ok]=1;
while(ok)
{
fr[a[0][ok]]=1;
ok=a[1][ok];
}
}
int main()
{ int nr=0;
f=fopen("dfs.in","r");
g=fopen("dfs.out","w");
citire();
for(int i=1;i<=n;i++)
if(!fr[i])
dfs(i),nr++;
fprintf(g,"%d",nr);
fclose(f);
fclose(g);
return 0;
}
