Cod sursa(job #2693390)

Utilizator bubblegumixUdrea Robert bubblegumix Data 5 ianuarie 2021 18:46:44
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include<fstream>
#include<list>
#include<stack>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> sol;
vector<int> partsol;
class graph
{
private:
	int n;
	list<int>* adj;
	void DFS(int n, int disc[], int low[], stack<int>* st, bool instack[]);
public:
	graph(int n);
	void addEdge(int x, int y);
	void getSCC();
};
graph::graph(int n)
{
	this->n = n;
	adj = new list<int>[n + 1];
}
void graph::addEdge(int x, int y)
{
	adj[x].push_back(y);
}
void graph::DFS(int u, int disc[], int low[], stack<int>* st, bool instack[])
{
	static int time = 0;
	disc[u] = low[u] = ++time;
	st->push(u);
	instack[u] = true;
	for (auto v : adj[u])
	{
		
		if (disc[v] == -1)
		{
			DFS(v, disc, low, st, instack);
			low[u] = min(low[u], low[v]);
		}
		else
			if(instack[u])
				low[u] = min(low[u], disc[v]);
	}

	if (low[u] == disc[u])
	{
		partsol.clear();
		int w = 0;
		while (st->top() != u)
		{
			w = st->top();
			partsol.push_back(w);
			instack[w] = false;
			st->pop();
		}
		w = st->top();
		partsol.push_back(w);
		instack[w] = false;
		st->pop();
		sol.push_back(partsol);
	}
	
}
void graph::getSCC()
{
	bool* instack = new bool[n + 1];
	int* disc = new int[n + 1];
	int* low = new int[n + 1];
	stack<int>* st = new stack<int>();
	for (int i = 1; i <= n; i++)
	{
		disc[i] = low[i] = -1;
		instack[i] = false;
	}
	for (int i = 1; i <= n; i++)
		if (disc[i] == -1)
			DFS(i, disc, low, st, instack);
	partsol.clear();
	while (!st->empty())
	{
		partsol.push_back(st->top());
		st->pop();
	}
	sol.push_back(partsol);
	fout << sol.size() << '\n';
	for (auto i : sol)
	{
		for (auto j : i)
			fout << j << " ";
		fout << '\n';
	}
	delete[] instack;
	delete st;
	delete[] disc;
	delete[] low;

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

	fin.close();
	fout.close();
	return 0;
}