Cod sursa(job #2928901)

Utilizator BrioflatorBalescu Alexandru Brioflator Data 24 octombrie 2022 04:27:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <map>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

class Graph {
public:
	int n;
	list<int>* adj_list;
	Graph(int n);
	void add_edge(int x, int y);
	Graph getTranspose();
	void DFS(int n,bool visited[]);
	void fillOrder(int node, stack<int>& stack, bool visited[]);
	void printCTC();
};

//Constructor cu parametru
Graph::Graph(int n)
{
	this->n = n;
	adj_list = new list <int>[n + 1];
 }

//metoda ajutatoare de adaugare de muchii
void Graph:: add_edge( int x, int y)
{
    adj_list[x].push_back(y); //adaugam y la lista lui x
}


// parcurgere dfs standard
void Graph:: DFS(int node, bool visited[])
{
	visited[node] = true;
	fout << node << " ";

	list<int>::iterator i;
	for (i = adj_list[node].begin(); i != adj_list[node].end(); i++)
		if (!visited[*i]) {
			DFS(*i, visited);

		}
}


// Transpunerea graafului
 Graph Graph::getTranspose()
{
	Graph g(n);
	for (int i = 1; i <= n; i++)
	{
		list<int>::iterator it;
		for (it = adj_list[i].begin(); it != adj_list[i].end(); it++) {
			g.adj_list[*it].push_back(i);
		}
	}
	return g;
}

void Graph::fillOrder( int node, stack<int>& stack, bool visited[])

{
	//nodul curent devine vizitat
	visited[node] = true;
	list<int>::iterator i;
	for (i = adj_list[node].begin(); i != adj_list[node].end(); i++)
		if (!visited[*i]) {
			fillOrder( *i, stack, visited);

		}

	//toate nodurile verificate au fost deja utilizate
	stack.push(node);
}

int counter = 0;

void Graph::printCTC()
{
	bool* visited = new bool[n];

	//marcam toate nodurile la inceput ca nevizitate
	stack<int> stack;
	for (int i = 1; i <= n; i++)
		visited[i] = false;

	//punem varfurile in stiva in functie de cum au fost parcursi
	for (int i = 1; i <= n; i++)
		if (visited[i] == false)
			fillOrder( i, stack, visited);

	//graf inversat
	Graph gr = getTranspose();

	for (int i = 1; i <= n; i++)
		visited[i] = false;

	//Folosim varfurile in functie de cum au intrat in stiva
	while (stack.empty() == false)
	{
		// Luam un varf din stiva
		int v = stack.top();
		stack.pop();

		// Zona unde afisam componentele tari conexe care contin varful
		if (visited[v] == false)
		{
			// Counter pentru a numara componentele tari conexe
			counter++;
			gr.DFS(v, visited);
			fout << endl;
		}

	}
	fout << counter;

}


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

		do
		{
			fin >> x >> y;
			g.add_edge(x, y);
		} while (x < 1 || x > n || y < 1 || y > n || x == y);

	}
	g.printCTC();

	return 0;
}