Pagini recente » Cod sursa (job #2135796) | Cod sursa (job #2145373) | Cod sursa (job #482750) | Cod sursa (job #1911563) | Cod sursa (job #161250)
Cod sursa(job #161250)
#include<stdio.h>
#define nmax 100000
typedef struct nod { int inf;
nod *urm;
};
nod *prim[nmax];
int viz[nmax];
int cnt,n,m;
void read()
{
int i,n1,n2;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d", &n, &m );
for(i=1;i<=m;i++)
{
scanf("%d%d", &n1, &n2);
nod *p= new nod;
p->inf=n1;
p->urm=prim[n2];
prim[n2]=p;
nod *q= new nod;
q->inf=n2;
q->urm=prim[n1];
prim[n1]=q;
}
}
void dfs(int nd)
{
viz[nd]=cnt;
for(nod *p=prim[nd]; p!=NULL; p=p->urm)
if(viz[p->inf]==0)
dfs(p->inf);
}
void solve()
{
int i;
for(i=1;i<=n;i++)
if(viz[i]==0)
{
++cnt;
dfs(i);
}
}
void print()
{
printf("%d\n", cnt);
}
int main()
{
read();
solve();
print();
return 0;
}