Cod sursa(job #2834783)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 17 ianuarie 2022 17:47:30
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 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<<'\n';
	
 
	
 
	
	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_front(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;
	
 
	
 
	
 
	
}