Cod sursa(job #1142789)

Utilizator myshuSpatariu Mihai-Constantin myshu Data 14 martie 2014 10:58:35
Problema Componente tare conexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include<fstream>
using namespace std;
ifstream fcin("ctc.in");
ofstream fcout("ctc.out");
class graf
{
		int noduri,muchii;
		int *c,**a;
		class nod
		{
			public:
				int info;
				nod *urm;
		};
		nod *n;
	public:
		graf()
		{
			noduri=0;
			muchii=0;
		}
		void citire()
		{
			int i,x,y;
			fcin>>x>>y;
			noduri=x;
			muchii=y;
			nod *poz[noduri+1],*p;
			n=new nod[noduri+1];
			c=new int[noduri+1];
			a=new int*[noduri+1];
			for(i=1;i<=noduri;i++)
				{
					a[i]=new int[noduri+1];
					n[i].info=0;
					n[i].urm=NULL;
					poz[i]=&n[i];
				}
			for(i=1;i<=muchii;i++)
				{
					fcin>>x>>y;
					p=new nod;
					p->info=y;
					p->urm=NULL;
					poz[x]->urm=p;
					poz[x]=p;
				}
		}
		void renew()
		{
			for(int i=1;i<=noduri;i++)
				n[i].info=0;
		}
		void df(int x)
		{
			nod *p;
			fcout<<x<<' ';
			n[x].info=1;
			p=&n[x];
			while(p->urm!=NULL)
				{
					p=p->urm;
					if(n[p->info].info==0)
						df(p->info);
				}
		}
		void bf(int x)
		{
			renew();
			int t=1,u=1;
			nod *p;
			c[1]=x;
			n[x].info=1;
			while(t<=u)
			{
				p=&n[c[t]];
				while(p->urm!=NULL)
				{
					p=p->urm;
					if(n[p->info].info==0)
					{
						c[++u]=p->info;
						n[p->info].info=n[c[t]].info+1;
					}
				}
				t++;
			}
		}
		void afisbf()
		{
			int p,t;
			p=1;
			for(t=1;t<=noduri;t++)
				if(p==n[c[t]].info)
					fcout<<c[t]<<' ';
				else
				{
					p=n[c[t]].info;
					fcout<<'\n'<<c[t]<<' ';
				}					
		}
		void matrice()
		{
			int i,t=1,u=1;
			for(i=1;i<=noduri;i++)
			{
				bf(i);
				for(t=1;t<=noduri;t++)
					a[i][t]=n[t].info-1;
			}
		}
		void afism()
		{
			int i,t;
			for(i=1;i<=noduri;i++)
			{
				for(t=1;t<=noduri;t++)
					fcout<<a[i][t]<<' ';
				fcout<<'\n';
			}
		}
		void conex()
		{
			int i,t=1,u=1;
			matrice();
			c[1]=1;c[0]=1;
			for(i=2;i<=noduri;i++)
				{
					int t=1,j;
					for(j=i-1;j>=1;j--)
						if(a[i][j]!=-1&&a[j][i]!=-1)
						{
							c[i]=c[i-1];
							t=0;
						}
					if(t==1)
						{c[i]=i;c[0]++;}
				}
		}
		void afiscon()
		{
			int i,t=c[1];
			fcout<<c[0]<<'\n';
			fcout<<t<<' ';
			for(i=2;i<=noduri;i++)
			{
				if(c[i]==t)
					fcout<<i<<' ';
				else
				{
					fcout<<'\n'<<i<<' ';
					t=c[i];
				}			
			}
		}
};
int main()
{
	graf t;
	t.citire();
	t.conex();
	t.afiscon();
	return 0;
}