Cod sursa(job #1962579)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 11 aprilie 2017 21:33:51
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <stack>

const int NMAX = 100005;

using namespace std;

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

int N, M;
int x, y;
vector <int> v[NMAX];
vector <int> vt[NMAX];
stack <int> S;
bool visited[NMAX];
vector <int> sols[NMAX];
int num_sol;

void print()
{
	g << num_sol << '\n';
	for (int i = 0; i < num_sol; ++i)
	{
		for (int j = 0; j < sols[i].size(); ++j)
		{
			g << sols[i][j] << " ";
		}
		g << '\n';
	}
}

void DFS(int node)
{
	visited[node] = true;
	for (int i = 0; i < v[node].size(); ++i)
	{
		int neigh = v[node][i];
		if (!visited[neigh])
		{
			DFS(neigh);
		}
	}
	S.push(node);
}

void DFSt(int node)
{
	sols[num_sol].push_back(node);
	visited[node] = true;
	for (int i = 0; i < vt[node].size(); ++i)
	{
		int neigh = vt[node][i];
		if (!visited[neigh])
		{
			DFSt(neigh);
		}
	}
}

void solve()
{
	for (int i = 1; i <= N; ++i)
	{
		if (!visited[i])
		{
			DFS(i);
		}
	}

	for (int i = 1; i <= N; ++i)
	{
		visited[i] = false;
	}

	while(!S.empty())
	{
		int node = S.top();
		S.pop();
		if (!visited[node])
		{
			DFSt(node);
			num_sol++;
		}
		else
		{
			S.pop();
		}
	}
}

void read()
{
	f >> N >> M;
	for (int i = 1; i <= M; ++i)
	{
		f >> x >> y;
		v[x].push_back(y);
		vt[y].push_back(x);
	}
}

int main()
{
	read();
	solve();
	print();
}