Cod sursa(job #954013)

Utilizator gabrieligabrieli gabrieli Data 27 mai 2013 23:07:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
/*
 * Componente tare conexe
 * Idee: algoritmul lui Tarjan
 */
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int index = 0;

void dfs (int v, const vector <vector <int>> &G,
		vector <int> &level, vector <int> &reach, stack <int> &visited,
		vector <bool> &seen, vector <vector <int>> &components)
{
	reach[v] = level[v] = index++;
	seen[v] = true;

	visited.push (v);

	for (size_t i = 0; i < G[v].size(); ++i)
		if (!seen[G[v][i]])
		{
			dfs (G[v][i], G, level, reach, visited, seen, components);

			reach[v] = min (reach[v], reach[G[v][i]]);
		}
		else
		{
			reach[v] = min (reach[v], reach[G[v][i]]);
		}

	if (level[v] == reach[v])
	{
		components.push_back (vector <int>());

		int x;
		do {
			x = visited.top();
			visited.pop();
            components.back().push_back (x);
		} while (x != v);
	}
}

int main()
{
	ifstream fin ("ctc.in");
	ofstream fout ("ctc.out");

	int n, m;

	fin >> n >> m;

	vector <vector <int>> G (n+1);
	for (; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back (y);
	}

	vector <bool> seen (n+1, false);
	vector <int> level (n+1), 
		   reach (n+1);
	stack <int> visited;
	vector <vector <int>> components;

	for (int i = 1; i <= n; ++i)
		if (!seen[i])
		{
			dfs (i, G, level, reach, visited, seen, components);
		}

	fout << components.size() << endl;
	for (size_t i = 0; i < components.size(); ++i)
	{
		for (size_t j = 0; j < components[i].size(); ++j)
			fout << components[i][j] << ' ' ;
		fout << endl;
	}

	fin.close();
	fout.close();
	return EXIT_SUCCESS;
}