Cod sursa(job #3345450)

Utilizator CreditKing69Bogdan Moldovan CreditKing69 Data 9 martie 2026 18:06:28
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <algorithm>

using namespace std;

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

int n, m,timer,cnt;
vector<vector<int>> graph,rez;
vector<int> disc, low;
vector<bool> inStack;
stack<int> st;

void dfs(int node)
{
	timer++;
	disc[node] = low[node] = timer;
	st.push(node);
	inStack[node] = true;
	for(int adj: graph[node])
	{
		if(disc[adj] == -1)
		{
			dfs(adj);
			low[node] = min(low[node], low[adj]);
		}
		else if(inStack[adj])
		{
			low[node] = min(low[node], disc[adj]);
		}
	}
	if(low[node] == disc[node])
	{
		cnt++;
		while (true)
		{
			int nd = st.top();
			st.pop();
			inStack[nd] = false;
			rez[cnt].push_back(nd);
			if (nd == node)
			{
				break;
			}
		}
	}
}

int main()
{
	in >> n >> m;
	graph.resize(n + 1);
	rez.resize(n + 1);
	disc.resize(n + 1);
	low.resize(n + 1);
	inStack.resize(n + 1, false);
	for(int i=1;i<=m; i++)
	{
		int x, y;
		in >> x >> y;
		graph[x].push_back(y);
	}
	for(int i=1; i<=n; i++)
	{
		if(disc[i]==0)
		{
			dfs(i);
		}
	}
	out << cnt << "\n";
	for(int i=1; i<=cnt; i++)
	{
		sort(rez[i].begin(), rez[i].end());
		for (int u : rez[i]) {
			out << u << " ";
		}
		out << "\n";
	}
}