Pagini recente » Cod sursa (job #2693410) | Borderou de evaluare (job #1330481) | oni_10_4 | Cod sursa (job #1043686) | Cod sursa (job #585190)
Cod sursa(job #585190)
#include<fstream>
using namespace std;
ofstream g("dfs.out");
int i,j,n,m,*a[101],x,y,p,q,b[101],v[101];
void dfs(int x)
{
//g<<x<<" ";
v[x]=1;
for(int i=1;i<=a[x][0];i++)
if(!v[a[x][i]])
dfs(a[x][i]);
}
int bfs(int x)
{
int i,st=0,dr=0,c[101];
v[x]=1;
c[0]=x;
//g<<x<<" ";
while(st<=dr)
{
x=c[st++];
for(i=1;i<=a[x][0];i++)
if(!v[a[x][i]])
{
v[a[x][i]]=3-v[x];
c[++dr]=a[x][i];
// g<<a[x][i]<<" ";
}
else
if(v[a[x][0]]==v[x])
return 0;
}
return 1;
}
void afis(int x)
{
int i,d[101],r=0;
if(v[x]==0)
g<<-1;
else
{
d[0]=x;
while(v[d[r]]!=-1)
d[++r]=v[d[r-1]];
for(i=r;i>=0;i--)
g<<d[i]<<" ";
}
}
void bfs1(int x,int y)
{
int i,st=0,dr=0,c[101];
v[x]=-1;
c[0]=x;
while(st<=dr&&v[y]==0)
{
x=c[st++];
for(i=1;i<=a[x][0];i++)
if(!v[a[x][i]])
{
v[a[x][i]]=x;
c[++dr]=a[x][i];
}
}
afis(y);
}
int dfs1(int x,int p)
{
int i;
v[x]=1;
for(i=1;i<=a[x][0];i++)
if(!v[a[x][i]])
{
if(dfs1(a[x][i],x)==0)
return 0;
}
else
if(p!=a[x][i])
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;
}
//bfs1(p,q);
int ok=0;
for(i=1;i<=n;i++)
if(!v[i])
{
ok++;
dfs(i);
}
g<<ok;
return 0;
}