Cod sursa(job #611644)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 2 septembrie 2011 15:39:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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(!indice[vecin]) 
			{DFS(vecin);lnk[nod]=min(lnk[nod],lnk[vecin]);}
		else if(vizitat[vecin]) lnk[nod]=min(lnk[nod],lnk[vecin]);
		}
	if(lnk[nod]==indice[nod])
		{solutie.push_back(stiva.back());
		vizitat[stiva.back()]=0;
		while(stiva.back()!=nod)
			{stiva.pop_back();
			vizitat[stiva.back()]=0;
			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(!indice[i])
			DFS(i);
	afis();
	return 0;	
}