Cod sursa(job #812034)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 13 noiembrie 2012 11:58:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.72 kb
#include<cstdio>
#include<cstdlib>
using namespace std;
int* gr[100001];
int* grt[100001];
int* ctc[100001];
bool viz[100001];
int postord[100001];
void dfs(int vf)
{
	int i;
	viz[vf]=1;
	for(i=1;i<=gr[vf][0];i++)
		if(!viz[gr[vf][i]])
			dfs(gr[vf][i]);
	postord[0]++;
	postord[postord[0]]=vf;
}
void dfst(int vf, int nct)
{
	int i;
	viz[vf]=0;
	ctc[nct][0]++;
	ctc[nct]=(int*)realloc(ctc[nct],(ctc[nct][0]+1)*4);
	ctc[nct][ctc[nct][0]]=vf;
	for(i=1;i<=grt[vf][0];i++)
		if(viz[grt[vf][i]])
			dfst(grt[vf][i],nct);
}
int main()
{
	int n,m,i,x,y,nct=0,j;
	freopen("ctc.in","r",stdin);
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=n;i++)
	{
		gr[i]=(int*)realloc(gr[i],4);
		grt[i]=(int*)realloc(grt[i],4);
		gr[i][0]=0;grt[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d %d\n",&x,&y);
		gr[x][0]++;
		gr[x]=(int*)realloc(gr[x],(gr[x][0]+1)*4);
		gr[x][gr[x][0]]=y;
		grt[y][0]++;
		grt[y]=(int*)realloc(grt[y],(grt[y][0]+1)*4);
		grt[y][grt[y][0]]=x;
	}
	fclose(stdin);
	for(i=1;i<=n;i++)
		if(!viz[i])
			dfs(i);
	for(i=n;i>0;i--)
		if(viz[postord[i]])
		{
			nct++;
			ctc[nct]=(int*)realloc(ctc[nct],4);
			ctc[nct][0]=0;
			dfst(postord[i],nct);
		}
	freopen("ctc.out","w",stdout);
	printf("%d\n",nct);
	for(i=1;i<=nct;i++)
	{
		for(j=1;j<=ctc[i][0];j++)
			printf("%d ",ctc[i][j]);
		printf("\n");
	}
	/*for(i=1;i<=postord[0];i++)
		g<<postord[i]<<" ";
	g<<'\n';*/
	fclose(stdout);
	return 0;
}

/*#include<fstream>
using namespace std;
int* gr[100001];
int* grt[100001];
int* ctc[100001];
bool viz[100001];
int postord[100001];
void dfs(int vf)
{
	int i;
	viz[vf]=1;
	for(i=1;i<=gr[vf][0];i++)
		if(!viz[gr[vf][i]])
			dfs(gr[vf][i]);
	postord[0]++;
	postord[postord[0]]=vf;
}
void dfst(int vf, int nct)
{
	int i;
	viz[vf]=0;
	ctc[nct][0]++;
	ctc[nct]=(int*)realloc(ctc[nct],(ctc[nct][0]+1)*4);
	ctc[nct][ctc[nct][0]]=vf;
	for(i=1;i<=grt[vf][0];i++)
		if(viz[grt[vf][i]])
			dfst(grt[vf][i],nct);
}
int main()
{
	int n,m,i,x,y,nct=0,j;
	ifstream f("ctc.in");
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		gr[i]=(int*)realloc(gr[i],4);
		grt[i]=(int*)realloc(grt[i],4);
		gr[i][0]=0;grt[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		gr[x][0]++;
		gr[x]=(int*)realloc(gr[x],(gr[x][0]+1)*4);
		gr[x][gr[x][0]]=y;
		grt[y][0]++;
		grt[y]=(int*)realloc(grt[y],(grt[y][0]+1)*4);
		grt[y][grt[y][0]]=x;
	}
	f.close();
	for(i=1;i<=n;i++)
		if(!viz[i])
			dfs(i);
	for(i=n;i>0;i--)
		if(viz[postord[i]])
		{
			nct++;
			ctc[nct]=(int*)realloc(ctc[nct],4);
			ctc[nct][0]=0;
			dfst(postord[i],nct);
		}
	ofstream g("ctc.out");
	g<<nct<<'\n';
	for(i=1;i<=nct;i++)
	{
		for(j=1;j<=ctc[i][0];j++)
			g<<ctc[i][j]<<" ";
		g<<'\n';
	}
	g.close();
	return 0;
}
*/