Cod sursa(job #545995)

Utilizator nautilusCohal Alexandru nautilus Data 4 martie 2011 11:15:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<vector>
#include<stack>
#define dmax 100010
#define inf 999999
using namespace std;

int n,m;
vector <int> a[dmax],ctc[dmax];
stack <int> s;
int index[dmax],lowlink[dmax];
bool ins[dmax];
int ind,nrctc;


void citire()
{
 int i,x,y;
	
 ifstream fin("ctc.in");
 fin>>n>>m;
 
 for (i=1; i<=m; i++)
	 {
	  fin>>x>>y;
	  a[x].push_back(y);
	 }	
 
 fin.close();
}


void strong(int nod)
{
 int i,w;
	
 index[nod] = lowlink[nod] = ind;
 ind++;
 s.push(nod); ins[nod] = 1;
 
 for (i=0; i<(int)a[nod].size(); i++)
	  if (index[a[nod][i]] == inf)
		 {
		  strong(a[nod][i]);
		  lowlink[nod] = min(lowlink[nod], lowlink[a[nod][i]]);
		 } else
		 if (ins[a[nod][i]] == 1)
			 lowlink[nod] = min(lowlink[nod], index[a[nod][i]]);
 
 if (index[nod] == lowlink[nod])
	 {
	  w = s.top();
	  ins[s.top()] = 0; s.pop(); 
	  
	  nrctc++;
	  ctc[nrctc].push_back(w);
	  
	  while (w != nod)
		  {
		   w = s.top();
	       ins[s.top()] = 0; s.pop(); 
		   ctc[nrctc].push_back(w);
		  }
	 }
}


void tarjan()
{
 int i;
 
 for (i=1; i<=n; i++)
	 index[i] = lowlink[i] = inf;
 
 for (i=1; i<=n; i++)
	 if (index[i] == inf)
		 strong(i);
}


void afisare()
{
 int i,j;
 
 ofstream fout("ctc.out");
 
 fout<<nrctc<<'\n';
 for (i=1; i<=nrctc; i++)
	 {
	  for (j=0; j<(int)ctc[i].size(); j++)
		 fout<<ctc[i][j]<<" ";
	  
	  fout<<'\n';
	 }
 
 fout.close();
}


int main()
{
	
 citire();
 tarjan();
 afisare();
	
 return 0;
}