Cod sursa(job #2928876)

Utilizator cilteaioanaIoana C cilteaioana Data 24 octombrie 2022 01:23:30
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

void dfs(int node, stack<int> &st, vector<int> &vis, vector<vector<int>> la)
{
	vis[node] = 1;
	for (auto it : la[node])
		if (!vis[it])
			dfs(it, st, vis, la);
	st.push(node);
}

vector<int> revDfs(int node, vector<int>& vis, vector<vector<int>> transp)//, ofstream& fout)
{
	vector<int> res;
	res.push_back(node);
	//fout << node << " ";
	vis[node] = 1;
	for (auto it : transp[node])
		if (!vis[it])
			revDfs(it, vis, transp);//, fout);
	//fout << endl;
	return res;
}

int main()
{
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");
	int n, m;
	fin >> n >> m;
	vector<vector<int>> la(n);
	for (int i = 0; i < m; i++)
	{
		int x, y;
		fin >> x >> y;
		la[x].push_back(y);
	}
	fin.close();
	stack<int> st;
	vector<int> vis(n, 0);
	for (int i = 0; i < n; i++)
		if (!vis[i])
			dfs(i, st, vis, la);
	
	vector<vector<int>> transp(n);

	for (int i = 0; i < n; i++)
	{
		vis[i] = 0;
		for (auto &it : la[i])
			transp[it].push_back(i);
	}
	
	vector<vector<int>> res;
	int n_comp = 0;
	while (!st.empty())
	{
		int node = st.top();
		st.pop();
		if (!vis[node])
		{
			//n_comp++;
			res.push_back(revDfs(node, vis, transp));//, fout);
			//fout << endl;
		}
	}
	fout << res.size() << endl;
	for (int i = 0; i < res.size(); i++)
	{
		for (int j = 0; j < res[i].size(); j++)
			fout << res[i][j] << ' ';
		fout << endl;
	}

	fout.close();
}