Cod sursa(job #2937905)

Utilizator EdgarPaun Andrei Edgar Data 11 noiembrie 2022 12:31:58
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.93 kb
//Complexitate: O(N+M)  
#include<bits/stdc++.h>
using namespace std;


	ifstream fin("ctc.in");
	ofstream fout("ctc.out");
int nrTotalComponente = 0;
int arrayNoduri[10000]; //pentru afisarea finala
int pozitiiDeNewline[10000];//pentru a stii cand trec la urnmatoarea CTC
int index;

void DFS1(int i,vector<int>& visited,stack<int>& stiva, vector<vector<int>>& listaAdiacenta)   // parcurgere DFS pe graful normal
{
	visited[i]=true;
	for(int j: listaAdiacenta[i])          //parcurgem folosind DFS din fiecare nod
		if(visited[j]==false)
			DFS1(j,visited,stiva,listaAdiacenta);

	stiva.push(i);  //cand finalizam o parcurgere DFS, punem nodul pe stiva , conform alg lui Kosaraju
}

void DFS2(int i,vector<int>& visited, vector<vector<int>>& listaReversed)  //DFS pe graful transpus
{

	arrayNoduri[index]=i;  // i-ul primit ca parametru este chiar nodul pe care trebuie sa il afisam 
						  // pentru a respecta ordinea afisarii din cerinta, salvez toate valorile, in ordinea in care trebuie afisate
						  // in array-ul arrayNoduri
	index++;
	visited[i] = true;
	for(int j: listaReversed[i])
		if(!visited[j])
			DFS2(j,visited,listaReversed);
}

void cautareCTC(vector<vector<int>>& listaAdiacenta, vector<vector<int>>& listaReversed, int n)
{
	stack<int> stiva;  //stiva pentru prima parcurgere DFS

	vector<int> visited(n+1,0);  //pentru nodurile vizitate
	for(int i=1;i<n+1;++i)
		if(!visited[i])
			DFS1(i,visited,stiva,listaAdiacenta);  //aplicam DFS pe nodurile nevizitate pentru a incarca stiva

	for(int i=1;i<n+1;++i)
		visited[i] = false;  //resetam array-ul de noduri vizitate pentru a doua parcurgere

	// cout<<"componente:\n";
	while(!stiva.empty())
	{
		int curr = stiva.top();
		stiva.pop();     //extragem primul element din stiva
		if(visited[curr]==0)  
		{
			DFS2(curr,visited,listaReversed);    //daca nodul e nevizitat aplicam DFS pe graful transpus din acel nod

			// cout<<index<<"\n";
			pozitiiDeNewline[index]=1; //unde va aparea valoarea 1 in acest array, acolo o sa dam newLine la afisare
			nrTotalComponente++;
		}
	}


	// fout<<nrTotalComponente<<"\n";
}

int main()
{


	int n,m;
	fin>>n>>m;

	vector<vector<int>> listaAdiacenta(n+1), listaReversed(n+1);

	for(int i=0;i<n;i++)
		arrayNoduri[i]=-1;



	for(int i=0;i<n;i++)
		pozitiiDeNewline[i]=-1;



	int x,y;
	while(m--){
		fin>>x>>y;
		listaAdiacenta[x].push_back(y);
		listaReversed[y].push_back(x);
	}


	cautareCTC(listaAdiacenta, listaReversed, n);

	fout<<nrTotalComponente<<'\n'; //mai intai afisam nr de componente
	for(int i=0;i<index;i++)
	{
		if(pozitiiDeNewline[i]==-1)
			fout<<arrayNoduri[i]<<" ";  //daca pozitiiDeNewline==-1 , inca suntem la aceeasi componenta
		else if(pozitiiDeNewline[i]==1)
			fout<<"\n"<<arrayNoduri[i]<<" "; //daca pozitiiDeNewline==1, am trecut la urmatoarea componenta
	}


	// for(int i=0;i<=index;i++)
	// 	cout<<pozitiiDeNewline[i]<<" ";
	return 0;
}