Cod sursa(job #2692489)

Utilizator bubblegumixUdrea Robert bubblegumix Data 2 ianuarie 2021 20:40:59
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include<iostream>
#include<list>
#include<stack>
#include<vector>
using namespace std;
vector<int> ps;
vector<vector<int>> ans;
class Graph
{
	int v;
	list <int>* adj;
	void DFS(int v, bool visited[]);
	void DFS2(int v, bool visited[],stack<int> &finishtime);
public:

	Graph(int v);
	void addEdge(int v, int w);
	Graph getTranspose();
	void printSCC();
};
Graph::Graph(int v)
{
	this->v = v;
	adj = new list<int>[v];
}
void Graph::DFS(int v, bool visited[])
{
	visited[v] = true;
	//cout << v << " ";
	for (auto it : adj[v])
		if (!visited[it])
			DFS(it, visited);
	ps.push_back(v);
}
void Graph::DFS2(int v, bool visited[], stack<int>& finishtime)
{
	visited[v] = true;

	for (auto it : adj[v])
		if (!visited[it])
			DFS2(it, visited,finishtime);
	finishtime.push(v);
	
}
void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);
}
Graph Graph::getTranspose()
{
	Graph g(v);
	for (int i = 0; i < v; i++)
	{
		for (auto it : adj[i])
			g.adj[it].push_back(i);
	}
	return g;
}
void Graph::printSCC()
{
	stack<int> Stack;
	bool* visited = new bool[v];
	for (int i = 0; i < v; i++)
		visited[i] = false;
	for (int i = 0; i < v; i++)
		if (visited[i] == false)
			DFS2(i, visited, Stack);

	Graph gr = getTranspose();
	for (int i = 0; i < v; i++)
		visited[i] = false;


	while (!Stack.empty())
	{
		int v = Stack.top();
		Stack.pop();
		if (visited[v] == false)
		{
			ps.clear();
			gr.DFS(v, visited);
			ans.push_back(ps);
			
		}
	}
	cout << ans.size()<<endl;
	for (auto i : ans)
	{
		for (auto j : i)
			cout << j << " ";
		cout << endl;
	}
}

int main()
{
	int n,m;
	cin >> n >> m;
	Graph g(n+1);
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		g.addEdge(x, y);
	}

	//cout << "SCC are:" << endl;
	g.printSCC();
}