Cod sursa(job #954024)

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

#define NMAX 100009

int index = 1, N;
int dfsIdx[NMAX], lowIdx[NMAX];
stack <int> ctcStack;
vector <int> G[NMAX];
vector <vector <int>> components;
bool inStack[NMAX];

void dfs (int v)
{
	dfsIdx[v] = lowIdx[v] = index++;
	ctcStack.push (v);
	inStack[v] = true;

	for (auto &n : G[v])
		if (dfsIdx[n] == 0)
		{
			dfs (n);
			lowIdx[v] = min (lowIdx[v], lowIdx[n]);
		}
		else if (inStack[n])
		{
			lowIdx[v] = min (lowIdx[v], lowIdx[n]);
		}

	if (dfsIdx[v] == lowIdx[v])
	{
		int n;
		components.push_back (vector <int>());
		do {
			n = ctcStack.top();
			ctcStack.pop();
			inStack[n] = false;
			components.back().push_back (n);
		} while (n != v);
	}
}

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

	fin >> N >> m;
	for (; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back (y);
	}

	for (int v = 1; v <= N; ++v)
		if (!dfsIdx[v])
		{
			dfs (v);
		}

	fout << components.size() << endl;
	for (auto &component : components)
	{
		for (auto &v : component)
			fout << v << ' ';
		fout << endl;
	}
    
	fin.close();
	fout.close();
	return EXIT_SUCCESS;
}