Cod sursa(job #2798632)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 11 noiembrie 2021 17:16:00
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 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];

bool visited_conex[N];

bool visited[N];



class Graph {

public:
	vector <int> adiacenta[N];
    stack <int> stiva;
    deque <int> dq;
	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(dq.size() != 0)
	{
        vf = dq.front();
        dq.pop_front();

		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]);

    dq.push_back(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;
    fin >> n >> m;

	Graph g;


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



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

	g.SolveConexe();

	return 0;



}