Cod sursa(job #954034)

Utilizator gabrieligabrieli gabrieli Data 28 mai 2013 00:03:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
/*
 * Componente tare conexe
 * Idee: algoritmul lui Tarjan
 */
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

#define NMAX 100009

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

void dfs (int v)
{
	dfsIdx[v] = lowIdx[v] = index++;
	ctcStack[ctcIdx++]= 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;
		do {
			n = ctcStack[--ctcIdx];
			inStack[n] = false;
			components[cmpIndex].push_back (n);
		} while (n != v);

		cmpIndex++;
	}
}

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 << cmpIndex << '\n';
	for (int c = 0; c < cmpIndex; ++c)
	{
		for (auto &v : components[c])
			fout << v << ' ';
		fout << '\n';
	}
    
	fout.close();
	return EXIT_SUCCESS;
}