Cod sursa(job #476832)

Utilizator vlad.maneaVlad Manea vlad.manea Data 12 august 2010 14:02:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

int N, M, K;
vector< vector<int> > Deg;
vector< set<int> > Com;
vector<int> Dfn, Low;
vector<bool> InS;
stack<int> Stk;

void read()
{
	int x, y;
	ifstream fin("ctc.in");

	fin >> N >> M;
	Deg.assign(N + 1, vector<int>());

	while (M--)
	{
		fin >> x >> y;
		Deg[x].push_back(y);
	}

	fin.close();
}

void tarjan(int u)
{
	int v;

	Low[u] = Dfn[u] = ++K;
	Stk.push(u);
	InS[u] = true;

	for (vector<int>::iterator i = Deg[u].begin(); i != Deg[u].end(); ++i)
	{
		v = *i;

		if (Dfn[v] == 0)
		{
			tarjan(v);
			Low[u] = min(Low[u], Low[v]);
		} 
		else if(InS[v])
		{
			Low[u] = min(Low[u], Dfn[v]);
		}
	}

	if (Low[u] == Dfn[u])
	{
		Com.push_back(set<int>());
		
		do
		{
			v = Stk.top();
			Stk.pop();
			InS[v] = false;
			Com[Com.size() - 1].insert(v);
		}
		while(v != u);
	}
}

void solve()
{
	Low.assign(N + 1, 0);
	Dfn.assign(N + 1, 0);
	InS.assign(N + 1, false);

	for (int i = 1; i <= N; ++i)
	{
		if (Dfn[i] == 0)
		{
			tarjan(i);
		}
	}
}

void write()
{
	ofstream fout("ctc.out");

	fout << Com.size() << '\n';

	for (vector< set<int> >::iterator i = Com.begin(); i != Com.end(); ++i)
	{
		for (set<int>::iterator j = i->begin(); j != i->end(); ++j)
		{
			fout << *j << ' ';
		}

		fout << '\n';
	}

	fout.close();
}

int main()
{
	read();
	solve();
	write();
	return 0;
}