Pagini recente » Cod sursa (job #1793576) | Cod sursa (job #585186)
Cod sursa(job #585186)
#include<fstream>
using namespace std;
ofstream g("dfs.out");
int n,m,i,j,*a[101],x,y,p,q,c[1001],ok;
int viz[101];
void df(int x)
{
int i;
//g<<x<<" ";
viz[x]=1;
for(i=1;i<=a[x][0];i++)
if(!viz[a[x][i]])
df(a[x][i]);
}
int bf(int x)
{
int i,prim,ultim;
// g<<x<<" ";
viz[x]=1;
c[0]=x;
prim=ultim=0;
while(prim<=ultim)
{
x=c[prim++];
for(i=1;i<=a[x][0];i++)
if(!viz[a[x][i]])
{
//g<<a[x][i]<<" ";
viz[a[x][i]]=3-viz[x];
c[++ultim]=a[x][i];
}
else
if(viz[a[x][i]]==viz[x])
return 0;
}
return 1;
}
int main()
{
ifstream f("dfs.in");
f>>n>>m;
for(i=1;i<=n;i++)
{
a[i]=(int *) realloc (a[i],sizeof(int));
a[i][0]=0;
}
while(f>>x>>y)
{
a[x][0]++;
a[x]=(int *) realloc (a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
a[y][0]++;
a[y]=(int *) realloc (a[y],(a[y][0]+1)*sizeof(int));
a[y][a[y][0]]=x;
}
ok=0;
for(i=1;i<=n;i++)
if(!viz[i])
{
df(i);
ok++;
}
g<<ok;
return 0;
}