Cod sursa(job #594244)
Utilizator | Data | 6 iunie 2011 18:46:38 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 35 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include<fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int t[2][5000],start[9999],viz[9999];
void df(int nod)
{int p;
p=start[nod];
viz[nod]=1;
while(p)
{if(viz[t[0][p]]==0)
df(t[0][p]);
p=t[1][p];
}
}
int main()
{int n,m,a,i,j,k=0,nr=0;
f>>n>>m;
for(a=1;a<=m;a++)
{f>>i>>j;
k++;
t[0][k]=j;
t[1][k]=start[i];
start[i]=k;
k++;
t[0][k]=i;
t[1][k]=start[j];
start[j]=k;
}
for(i=1;i<=n;i++)
if(viz[i]==0)
{df(i); nr++; }
g<<nr;
return 0;
}