Cod sursa(job #1609799)

Utilizator ArkinyStoica Alex Arkiny Data 23 februarie 2016 00:23:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

vector<int> s;

vector<int> L1[100010];
vector<int> L2[100010];

bitset<100010> v;
vector<int> vec[100010];
int nr = 0;
void DFS1(int x)
{
	v[x] = 1;
	for (int i = 0;i < L1[x].size();++i)
		if (v[L1[x][i]] == 0)
			DFS1(L1[x][i]);
	s.push_back(x);

}
void DFS2(int x)
{
	v[x] = 1;
	for (int i = 0;i < L2[x].size();++i)
		if (v[L2[x][i]] == 0)
			DFS2(L2[x][i]);
	vec[nr].push_back(x);
}

int main()
{
	int N,M;

	in >> N >> M;
	for (int i = 1;i <= M;++i)
	{
		int x, y;
		in >> x >> y;
		L1[x].push_back(y);
		L2[y].push_back(x);
	}
	for (int i = 1;i <= N;++i)
	{
		if (v[i] == 0)
			DFS1(i);
	}
	v.reset();
	for (int i = N-1;i >=0;--i)
	{
		if (v[s[i]] == 0)
		{
			++nr;
			DFS2(s[i]);
		}
	}
	out << nr << '\n';
	for (int i = 1;i <= nr;++i)
	{
		for (int j = 0;j < vec[i].size();++j)
			out << vec[i][j] << " ";
		out << '\n';
	}
	return 0;
}