Cod sursa(job #2797874)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 10 noiembrie 2021 18:19:41
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>
#define N 100001
using namespace std;


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


vector <int> conexe[N];
stack <int> stiva;

bool visited_conex[N];
bool visited[N];

class Graph {
public:

	vector <int> adiacenta[N];
	vector <int> adiacenta_conex[N];


	void addEdge(int x, int y);
    void SolveConexe();
    void DFS_CNX(int vf, int ctc);
	void DFS(int vf);

};

void Graph::addEdge(int x, int y)
{
     adiacenta[x].push_back(y);
     adiacenta_conex[y].push_back(x);
}

void Graph::SolveConexe()
{

	int vf, ctc = 0;

	while(!stiva.empty())
	{
        stiva.pop();
		vf = stiva.top();

		if(visited_conex[vf] == 0)
		{
			ctc += 1;
			DFS_CNX(vf, ctc);
		}
	}

	fout<<ctc<<endl;

	for(int i = 1; i <= ctc; ++i)
	{
		for(int j = 0; j < conexe[i].size(); ++j)
        {
				fout<<conexe[i][j]<<" ";
        }
		fout<<endl;
	}

}

void Graph::DFS(int vf)
{

	visited[vf] = true;

	for(int i = 0; i < adiacenta[vf].size(); ++i)
		if(!visited[adiacenta[vf][i]])
			DFS(adiacenta[vf][i]);

    stiva.push(vf);
}

void Graph::DFS_CNX(int vf,int ctc)
{
	visited_conex[vf] = 1;
	conexe[ctc].push_back(vf);

	for(int i = 0; i < adiacenta_conex[vf].size(); ++i)
		if(visited_conex[adiacenta_conex[vf][i]] == 0)
			DFS_CNX(adiacenta_conex[vf][i], ctc);

}


int main()
{

	int n, m, n1, n2;

    cin >> n >> m;

	Graph g;

    for(int i = 0; i < m; ++i)
    {
        cin >> n1 >> n2;
        g.addEdge(n1,n2);
    }

    for(int i = 1; i <= n; ++i)
    {
        if(!visited[i])
			g.DFS(i);
    }

	g.SolveConexe();


	return 0;

}