Competitive-Coding/kosarajasAlgorithm.cpp at master · psdhanesh7/Competitive-Coding · 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;

void dfs(vector<int> *edges, int currVertex, bool *visited, stack<int> &finishedVertices)
{
	visited[currVertex] = true;

	for(int i = 0; i < edges[currVertex].size(); i++)
	{
		int adjacent = edges[currVertex][i];
		if(!visited[adjacent])
		{
			dfs(edges, adjacent, visited, finishedVertices);
		}
	}

	finishedVertices.push(currVertex);
}

void dfs2(vector<int> *edges, int currVertex, bool *visited, unordered_set<int>* component)
{
	visited[currVertex] = true;
	component->insert(currVertex);

	for(int i = 0; i < edges[currVertex].size(); i++)
	{
		int adjacent = edges[currVertex][i];
		if(!visited[adjacent])
		{
			dfs2(edges, adjacent, visited, component);
		}
	}
}

unordered_set<unordered_set<int>*>* getStronglyConnectedComponents(vector<int> *edges, vector<int> *edgesT, int n)
{
	bool *visited = new bool[n]();
	stack<int> finishedVertices;

	for(int i = 0; i < n; i++)
	{
		if(!visited[i])
		{
			dfs(edges, i, visited, finishedVertices);
		}
	}

	delete [] visited;
	visited = new bool[n]();

	unordered_set<unordered_set<int>*>* output = new unordered_set<unordered_set<int>*>();

	while(!finishedVertices.empty())
	{
		int element = finishedVertices.top();
		finishedVertices.pop();

		if(visited[element])
		{
			continue;
		}
		unordered_set<int>* component = new unordered_set<int>();

		dfs2(edgesT, element, visited, component);
		output->insert(component);
	}
	delete [] visited;

	return output	;
}

int main()
{
	int n;
	cin >> n;

	vector<int> *edges = new vector<int>[n];
	vector<int> *edgesT = new vector<int>[n];

	int m;
	cin >> m;

	for(int i = 0; i < m; i++)
	{
		int j, k;
		cin >> j >> k;

		edges[j-1].push_back(k-1);
		edgesT[k-1].push_back(j-1);
	}

	unordered_set<unordered_set<int>*> *components = getStronglyConnectedComponents(edges, edgesT, n);

	unordered_set<unordered_set<int>*> :: iterator it = components->begin();
	while(it != components->end())
	{
		unordered_set<int>* component = *it;

		unordered_set<int> :: iterator it2 = component->begin();
		while(it2 != component->end())
		{
			cout << *it2 + 1 << " ";
			it2++;
		}
		cout << endl;
		delete component;
		it++;
	}

	delete [] edges;
	delete [] edgesT;
	delete components;

	return 0;
}