Algorithms/connected_components.cc at master · iamghazi/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <list>

using namespace std;


class Graph{
	int V;
	list<int> *A;
public:
	Graph(int v);
	void addEdge(int s, int d);
	int vertex() { return V;}
	friend void BFS(Graph G, int s, bool* X);
};

Graph::Graph(int v){
	this->V = v;
	A = new list<int>[V];
}

void Graph::addEdge(int s, int d){
	A[s].push_back(d);
	A[d].push_back(s);
}

void BFS(Graph G, int s, bool* X){
	list<int> queue;
	X[s] = true;
	queue.push_back(s);
	int temp;
	while(!queue.empty()){
		temp = queue.front();
		queue.pop_front();
		for(list<int>::iterator i = G.A[temp].begin();i != G.A[temp].end();i++){
			if(X[*i]==false){
				X[*i] = true;
				queue.push_back(*i);

			}
		}
	}

}


int main(){

	Graph G(10);
	G.addEdge(0,4);
	G.addEdge(0,2);
	G.addEdge(2,4);
	G.addEdge(3,5);
	G.addEdge(6,8);
	G.addEdge(1,3);
	G.addEdge(5,7);
	G.addEdge(5,9);
	G.addEdge(7,9);

	bool* visited = new bool[G.vertex()];
	for(int i=0;i<G.vertex();i++){
		visited[i] = false;
	}

	int count = 0;

	for(int i=0;i<G.vertex();i++){
		if(visited[i]==false){
			BFS(G,i,visited);
			count++;
		}
	}

	cout << count << endl;
}