Cod sursa(job #1216652)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 5 august 2014 11:39:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> A[200001];
vector <int> At[200001];
vector <int> C[200001];
stack <int> S;
int N, M,nrc;
int i, a, b;
int viz[200001];
void df(int v)
{
	vector <int>::iterator it;
	int w;
	viz[v] = 1;
	for (it = A[v].begin(); it != A[v].end(); it++)
	{
		w = *it;
		if (!viz[w])
			df(w);
	}
	S.push(v);
}

void ctc(int v)
{
	vector<int>::iterator it;
	viz[v] = 1;
	int w;
	C[nrc].push_back(v);
	for (it = At[v].begin(); it != At[v].end(); it++)
	{
		w = *it;
		if(!viz[w])
			ctc(w);
	}
}

int main()
{
	f >> N >> M;
	for (i = 1; i <= M; i++)
	{
		f >> a >> b;
		A[a].push_back(b);
		At[b].push_back(a);
	}
	for (i = 1; i <= N; i++)
		if (!viz[i])
			df(i);
	for (i = 1; i <= N; i++)
		viz[i] = 0;
	while (!S.empty())
	{
		int v;
		v = S.top();
		S.pop();
		if (!viz[v])
		{
			nrc++;
			ctc(v);
		}
	}
	g << nrc << '\n';
	for (i = 1; i <= nrc; i++)
	{
		vector<int>::iterator it;
		for (it = C[i].begin(); it != C[i].end(); it++)
			g << *it << ' ';
		g << '\n';
	}
	f.close();
	g.close();
	return 0;
}