Cod sursa(job #727017)

Utilizator algotrollNume Fals algotroll Data 27 martie 2012 18:10:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<sstream>
#include<stack>
#include<vector>
#define _NM 100010
using namespace std;

bool viz[_NM];
void dfs(vector<int> vAd[], int nod, stack<int> &enu)
{
	if (viz[nod]) return;
	viz[nod]=1;
	for (vector<int>::iterator it=vAd[nod].begin();it!=vAd[nod].end();++it)
		dfs(vAd,*it,enu);
	enu.push(nod);
}

int main()
{
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");
	int nN, nM;
	fin>>nN>>nM;
	static vector<int> vAd[_NM], vAd_t[_NM];
	for (int i=1;i<=nM;i++)
	{
		int nod1, nod2;
		fin>>nod1>>nod2;
		vAd[nod1].push_back(nod2);
		vAd_t[nod2].push_back(nod1);
	}
	stack<int> order;
	for (int i=1;i<=nN;i++)
		dfs(vAd,i,order);
	//global viz
	for (int i=1;i<=nN;i++) viz[i]=0;
	
	stringstream ss; int sol_cnt=0;
	while (!order.empty())
	{
		stack<int> sol;
		dfs(vAd_t,order.top(),sol);
		order.pop();
		if (!sol.empty())
		{
			sol_cnt++;
			while (!sol.empty())
			{
				ss<<sol.top()<<' ';
				sol.pop();
			}
			ss<<'\n';
		}
	}
	fout<<sol_cnt<<'\n'<<ss.str();
	return 0;
}