Cod sursa(job #2326612)

Utilizator VladFetitoiu_FMI_UVTVlad Fetitoiu VladFetitoiu_FMI_UVT Data 23 ianuarie 2019 18:51:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
using namespace std;
ofstream out("dfs.out");
ifstream in("dfs.in");
ifstream file("dfs.in");

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()
{

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];


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);

out<<componente<<"\n";

out.close();
return 0;
}