Pagini recente » Borderou de evaluare (job #528070) | Rating Chelaru Gabriela (GabrielaChelaru) | Cod sursa (job #2373055) | Clasament your11thnightmare | Cod sursa (job #881704)
Cod sursa(job #881704)
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
long n,r;
long long m;
long long c[100000];
long long viz[100000];
struct nod {
long long j;
nod *urm;
};
nod *g[100000];
void cit()
{
int i,j;
nod *p;
fin>>n>>m;
while(fin>>i>>j)
{
p=new nod;
p->j=j;
p->urm=g[i];
g[i]=p;
}
fin.close();
}
void tipar ()
{int i;
nod *p;
for(i=1;i<=n;i++)
{
fout<<i<<" ";
p=g[i];
while(p)
{
fout<<p->j<<" ";
p=p->urm;
}
fout<<'\n';
}
}
void bf(int r,int nc)
{
int p,u,vf;
c[1]=r;
p=u=1;
nod *d;
viz[r]=nc;
while(p<=u)
{
vf=c[p];
d=new nod;
d=g[vf];
while(d)
{
if(viz[d->j]==0)
{
u++;
c[u]=d->j;
viz[d->j]=nc;
}
d=d->urm;
}
p++;
}
}
int main()
{
cit();
int i;
int nc=0;
for(i=1;i<=n;i++)
if(viz[i]==0)
{
nc++;
bf(i,nc);
}
fout<<nc;
return 0;
}