Cod sursa(job #2561091)

Utilizator Iulia25Hosu Iulia Iulia25 Data 28 februarie 2020 16:25:39
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int N=10003;
int ctc[N],viz[N],vizinv[N];

struct nod
{
 int et;
 nod* adr;
};
struct stiva
{
 int et;
 stiva *adr;
} *ct[N];
nod* l[N],*inv[N];
int c=0;
void dfs(int x, int k)
{
 viz[x]=k;
 for(nod* a=l[x];a!=NULL;a=a->adr)
 {
  if(viz[a->et]!=k)
   {
    viz[a->et]=k;
    dfs(a->et,k);
   }
 }
}
void dfsinv(int y,int k)
{
 vizinv[y]=k;
 for(nod* b=inv[y];b!=NULL;b=b->adr)
  {
    if(vizinv[b->et]!=k)
    {
     vizinv[b->et]=k;
     dfsinv(b->et,k);
    }
	}
 if(viz[y]==k && vizinv[y]==k)
 {
	ctc[y] = k;
	stiva *p = new stiva;
	p -> et = y;
	p -> adr = ct[k];
	ct[k] = p;
 }
}
int main()	{
  int n,m,x,y;
  fin>>n>>m;
  for(int i=1;i<=m;++i)
  {
   fin>>x>>y;
   nod* p=new nod;
   p->et=y;
   p->adr=l[x];
   l[x]=p;
   p=new nod;
   p->et=x;
   p->adr=inv[y];
   inv[y]=p;
  }
  int k = 0;
  for(int i=1;i<=n;++i)
  {
	 if(ctc[i]==0)
	 {
	 ++k;
	  dfs(i, k);
	  dfsinv(i, k);
	 }
  }
  fout << k << '\n';
  for (int i = 1; i <= k; ++i)	{
		for (stiva *a = ct[i]; a != NULL; a = a -> adr)	 {
			fout << a->et << ' ';
		}
		fout << '\n';
	}
}