Cod sursa(job #2641822)

Utilizator llama27Asd asd llama27 Data 12 august 2020 19:03:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <queue>
#include <cmath>
#include <string>
#include <stack>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");
#define NMAX 100005
#define UNVISITED -1

int index, scc;
vector<int> g[NMAX], ids, lowlink, temp;
vector<vector<int>> sol;
stack<int> s;
vector<bool> inStack;
int n, m;


void read()
{
	for (in >> n >> m; m--;)
	{
		int x, y;
		in >> x >> y;
		g[x].push_back(y);
	}
	ids.resize(n + 5), ids.assign(n + 5, UNVISITED);
	inStack.resize(n + 5), inStack.assign(n + 5, 0);
	lowlink.resize(n + 5);
}


void tarjan(int node)
{
	ids[node] = lowlink[node] = index++;
	s.push(node);
	inStack[node] = true;

	for (int it = 0; it < g[node].size(); it++)
	{
		int adjNode = g[node][it];
		if (ids[adjNode] == UNVISITED)
		{
			tarjan(adjNode);
			lowlink[node] = min(lowlink[node], lowlink[adjNode]);
		}
		else if (inStack[adjNode])
			lowlink[node] = min(lowlink[node], lowlink[adjNode]);
	}

	if (ids[node] == lowlink[node])
	{
		temp.clear();
		int nd;
		do
		{
			nd = s.top();
			temp.push_back(nd);
			s.pop();
			inStack[nd] = false;

		} while (nd != node);
		sol.push_back(temp);
	}
}

void print()
{
	out << sol.size() << '\n';
	for (vector<int> it : sol)
	{
		copy(it.begin(), it.end(), ostream_iterator<int>(out, " "));
		out << '\n';
	}
}

void solve()
{
	read();
	for (int i = 1; i <= n; i++)
		if (ids[i] == UNVISITED)
			tarjan(i);

	print();
}

int main()
{
	solve();
}