Cod sursa(job #3372206)

Utilizator Alex112358Glavan Alexandru Alex112358 Data 2 noiembrie 2026 18:44:59
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int N, M, arce[5001][5001], nrComponente, adaugat[5001];
vector<vector<int>> componenete;

int main() {

	f >> N >> M;
	componenete.resize(5001);
	for (int i = 1; i <= M; i++)
	{
		int n1, n2;
		f >> n1 >> n2;
		arce[n1][n2] = 1;
	}

	for (int nodInt = 1; nodInt <= N; nodInt++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (arce[i][nodInt] == 1 && arce[nodInt][j] == 1)
					arce[i][j] = 1;
	
	for (int i = 1; i <= N; i++)
	{
		if (adaugat[i] == 0)
		{
			adaugat[i] = 1;
			nrComponente++;
			componenete[nrComponente].push_back(i);
			for (int j = 1; j <= N; j++)
				if (arce[i][j] && arce[j][i] && adaugat[j] == 0)
				{
					componenete[nrComponente].push_back(j);
					adaugat[j] = 1;
				}
				
		}
	}

	for (int i = 1; i <= nrComponente; i++)
	{
		g << "Componenta " << i << " : ";
		for (auto nod : componenete[i])
			g <<  nod<< " ";
		g << "\n";
	}
	return 0;
}