Pagini recente » Cod sursa (job #3222749) | Cod sursa (job #2446632) | Cod sursa (job #1174121) | Cod sursa (job #641492) | Cod sursa (job #2318885)
#include <string.h>
#include <fstream>
#define nmax 100000
using namespace std;
int n,m,viz[nmax+5],cnt=0;
struct nod
{
int info;
nod *urm;
}*v[nmax+5],*c[nmax+5],*d;
void baga(const int &x,const int &y)
{
if(!v[x])
{
v[x]=new nod;
v[x]->info=x;
c[x]=new nod;
c[x]->info=y;
c[x]->urm=0;
v[x]->urm=c[x];
}
else
{
d=new nod;
d->info=y;
d->urm=0;
c[x]->urm=d;
c[x]=d;
}
if(!v[y])
{
v[y]=new nod;
v[y]->info=y;
c[y]=new nod;
c[y]->info=x;
c[y]->urm=0;
v[y]->urm=c[y];
}
else
{
d=new nod;
d->info=x;
d->urm=0;
c[y]->urm=d;
c[y]=d;
}
}
void dfs(int k)
{
viz[k]=1;
cnt++;
nod *e;
e=v[k];
while(e->urm)
{
e=e->urm;
if(!viz[e->info])
dfs(e->info);
}
}
int main()
{
int x,y,s=0;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin>>n>>m;
memset(v,0,sizeof(v));
memset(c,0,sizeof(c));
while(fin>>x>>y)
baga(x,y);
for(int i=1;i<=n;i++)
{
if(!viz[i] && v[i])
{s++;dfs(i);}
}
fout<<s+n-cnt;
return 0;
}