Pagini recente » Cod sursa (job #1338640) | Cod sursa (job #74925) | Cod sursa (job #76677) | Cod sursa (job #2045327) | Cod sursa (job #177469)
Cod sursa(job #177469)
#include <fstream>
using namespace std;
long v[100001],coada[100001],v1[100001],comp[100001],componente;
long *c[100001];
long j,i,n;
void dfs(int nod)
{
componente++;
long p=1,u=1;
comp[i]=componente;
coada[p]=nod;
while(p<=u)
{
for(long z=1;z<=v[coada[p]];z++)
{
if(comp[c[coada[p]][z]]!=componente)
{
comp[c[coada[p]][z]]=componente;
u++;
coada[u]=c[coada[p]][z];
}
}
p++;
}
}
int main()
{
ifstream in("dfs.in");
long x,y,m;
in>>n>>m;
for(i=1;i<=m;i++)
{
in>>x>>y;
v[x]++;
v[y]++;
}
in.close();
for(i=1;i<=n;i++)
c[i]=new long[v[i]+1];
ifstream file("dfs.in");
file>>n>>m;
for(i=1;i<=m;i++)
{
file>>x>>y;
c[x][v1[x]+1]=y;
v1[x]++;
c[y][v1[y]+1]=x;
v1[y]++;
}
file.close();
for(i=1;i<=n;i++)
if(v[i]==0) comp[i]=++componente;
else if(comp[i]==0) dfs(i);
ofstream out("dfs.out");
out<<componente<<"\n";
//for(i=1;i<=n;i++) cout<<comp[i]<<" ";
/*for(i=1;i<=n;i++)
{
for(j=1;j<=v[i];j++)
out<<c[i][j]<<" ";
out<<"\n";
}
*/
out.close();
return 0;
}