#include "../../snap-core/Snap.h"
#include <stdio.h>

THashSet<TInt> done;

//BFS from starter and return the size of this connected component
int bfs(PUNGraph g, int starter)
{
	TQQueue<TInt> q;
	int ccsize=0;
	q.Push(starter);
	++ccsize;
	done.AddKey(starter);
	while (!q.Empty())
	{
		TUNGraph::TNodeI p=g->GetNI(q.Top());
		q.Pop();
		for (int i=0; i<p.GetDeg(); ++i)
			if (!done.IsKey(p.GetNbrNId(i)))
			{
				done.AddKey(p.GetNbrNId(i));
				q.Push(p.GetNbrNId(i));
				++ccsize;
			}
	}
	return ccsize;
}

int main(int argc, char* argv[]) {
	PUNGraph g = TSnap::GenRndGnm<PUNGraph>(100, 100);
	
	printf("We have connected components of these sizes:\n");
	for (int i=0; i<g->GetNodes(); ++i)
		if (!done.IsKey(i))  //not BFSed yet
		{
			int ccsize = bfs(g, i);
			printf(" %d", ccsize);
		}

	printf("\n");
    return 0;
}