Cod sursa(job #2897417)

Utilizator ClaudiuChelceaClaudiuChelcea ClaudiuChelcea Data 3 mai 2022 18:30:25
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <vector>
#define MaxN 100009
 
using namespace std;
 
vector <int> suc[MaxN],pred[MaxN],sol[MaxN];
int n,m,uz[MaxN],c[MaxN],nr,sz;
 
void cit()
{
	int i,x,y;
	freopen("ctc.in","r",stdin);
	scanf("%d%d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		suc[x].push_back(y);
		pred[y].push_back(x);
	}
}
 
void dfs(int nod)
{
	int i,p;
	uz[nod]=1;
	
	for(i=0;i<suc[nod].size();i++)
	{
		p=suc[nod][i];
		if(!uz[p])
			dfs(p);
	}
	
	sz++;
	c[sz]=nod;
}
 
void df(int nod,int nr)
{
	int i,p;
	uz[nod]=1;
	
	sol[nr].push_back(nod);
 
	for(i=0;i<pred[nod].size();i++)
	{
		p=pred[nod][i];
		if(!uz[p])
			df(p,nr);
	}
}	
 
void afis()
{
	int i,j;
	freopen("ctc.out","w",stdout);
	printf("%d\n",nr);
	for(i=1;i<=nr;i++)
	{
		for(j=0;j<sol[i].size();j++)
			printf("%d ",sol[i][j]);
		printf("\n");
	}
}
 
int main()
{
	cit();
	for(int i=1;i<=n;i++)
		if(!uz[i])
			dfs(i);
		
	memset(uz,0,sizeof(uz));
	
	for(int i=sz;i;i--)
		if(!uz[c[i]])
		{
			nr++;
			df(c[i],nr);
		}
		
	afis();
 
	return 0;
}