Cod sursa(job #472615)

Utilizator cosmyoPaunel Cosmin cosmyo Data 25 iulie 2010 20:53:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream.h>
#include<list>
#define Nmax 100009
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
LI a[Nmax],at[Nmax];
long n,m,nrc,v[Nmax],po[Nmax],nr;
void cit()
{ifstream fin("ctc.in");
  fin>>n>>m;
  long i,x,y;
	  for(i=1;i<=m;++i)
	  {fin>>x>>y;
	   a[x].push_back(y);
	   at[y].push_back(x);
	  }
  fin.close();
}
void dfs(long k)
{IT it;
 v[k]=1;
	 for(it=a[k].begin();it!=a[k].end();++it)
		 if(v[*it]==0)
			 dfs(*it);
 ++nr;po[nr]=k;
}
void dfst(long k)
{IT it;
 v[k]=-nrc;
  for(it=at[k].begin();it!=at[k].end();++it)
	  if(v[*it]==1)
		  dfst(*it);
}
ofstream fout("ctc.out");
void dfstafis(long k)
{IT it;
 v[k]=-nrc;
 fout<<k<<" ";
  for(it=at[k].begin();it!=at[k].end();++it)
	  if(v[*it]==1)
		  dfstafis(*it);
}
void afis()
{long i,j;
 
  for(i=1;i<=n;++i)
	  if(v[i]==0)
		  dfs(i);
  for(i=n;i>=1;--i)
   if(v[po[i]]==1)
   {++nrc;
	dfst(po[i]);
   }
  fout<<nrc<<'\n';
 for(i=1;i<=n;++i)
	 v[i]=1;
 nrc=0;
 for(i=n;i>=1;--i)
	 if(v[po[i]]==1)
	 {++nrc;
	  dfstafis(po[i]);
	  fout<<'\n';
	 }
 fout.close();
}
int main()
{cit();
 afis();
 return 0;
}