Cod sursa(job #611638)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 2 septembrie 2011 15:11:25
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<vector>
#define mx 200200
using namespace std;
vector<int> v[mx],stiva,solutie,stop;
int lnk[mx],vizitat[mx],indice[mx],n,nr=1;
void afis() {
	int i,j=0,m=solutie.size();
	ofstream out("ctc.out");
	out<<stop.size()<<'\n';
	for(i=0;i<m;i++)
		{out<<solutie[i]<<" ";
		if(stop[j]==i)
			out<<'\n',j++;
		}
	out.close();
}
void DFS(int nod) {
	int vecin,i,m=v[nod].size();
	vizitat[nod]=1;
	indice[nod]=nr;
	lnk[nod]=nr++;
	stiva.push_back(nod);
	for(i=0;i<m;i++)
		{vecin=v[nod][i];
		if(!vizitat[vecin]) 
			DFS(vecin);
		lnk[nod]=min(lnk[nod],lnk[vecin]);
		}
	if(lnk[nod]==indice[nod])
		{solutie.push_back(stiva.back());
		while(stiva.back()!=nod)
			{stiva.pop_back();
			solutie.push_back(stiva.back());
			}
		stiva.pop_back();
		stop.push_back(solutie.size()-1);
		}
}
void citire() {
	int i,m,x,y;
	ifstream in("ctc.in");
	in>>n>>m;
	for(i=0;i<m;i++)
		{in>>x>>y;
		v[x].push_back(y);
		}
	in.close();
}
int main() {
	int i;
	citire();
	for(i=1;i<=n;i++)
		if(!vizitat[i])
			DFS(i);
	afis();
	return 0;	
}