Cod sursa(job #2209300)

Utilizator jurjstyleJurj Andrei jurjstyle Data 2 iunie 2018 17:37:10
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <list>
#include <algorithm>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int NMAX = 100002;

int N, M;
vector <int> G[NMAX];
stack <int> St;
vector <bool> Viz;
vector <int> Nivel, Length, Comp_curent;
vector <vector <int>> Cc;
int nv;

void DFS(int);

int main()
{
	f >> N >> M;
	Viz = vector <bool>(N + 1, 0);
	Nivel = Length = vector <int>(N + 1, 0);
	for (int i = 1; i <= M; ++i)
	{
		int x, y;
		f >> x >> y;
		G[x].push_back(y);
	}

	for (int i = 1; i <= N; ++i)
		if (Nivel[i] == 0)
			DFS(i);
	g << Cc.size() << "\n";
	for (int i = 0; i < Cc.size(); ++i)
	{
		for (const int & j : Cc[i])
			g << j << " ";
		g << "\n";
	}
	f.close();
	g.close();
	return 0;
}


void DFS(int x)
{
	Viz[x] = true;
	St.push(x);
	Nivel[x] = Length[x] = ++nv;
	for (const int & y : G[x])
		if (Nivel[y] == 0) //daca e muchie de arbore
		{
			DFS(y);
			Length[x] = min(Length[x], Length[y]);
		}
		else //if (Viz[y] == true) //daca e muchie de intoarcere
			Length[x] = min(Length[x], Nivel[y]);
	if (Nivel[x] == Length[x])
	{ 
		Comp_curent.clear();
		while (true)
		{
			int nod_curent = St.top();
			Comp_curent.push_back(nod_curent);
			Viz[nod_curent] = false;
			St.pop();
			if (x == nod_curent)
				break;
		}
		Cc.push_back(Comp_curent);
	}
}