Cod sursa(job #744375)

Utilizator lucian666Vasilut Lucian lucian666 Data 8 mai 2012 15:39:10
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb


#include<fstream>
#include<vector>
#include<cstring>
#include<algorithm>

#define NN 100001
#define pb push_back

using namespace std;
ofstream out("ctc.out");

vector<int>G1[NN];
vector<int>G2[NN];
typedef vector<int>:: iterator IT;

int n,m,v1[NN],v2[NN],c[NN];
void citire()
{
	ifstream in("ctc.in");
	in>>n>>m;
	int i,j;
	for(;m;--m)
	{
		in>>i>>j;
		G1[i].pb(j);
		G2[j].pb(i);
	}
}


void DFS(vector<int>*g,int start ,int n ,int v[100])
{
	v[start]=1;
			for(vector<int>::iterator i=g[start].begin();i<g[start].end();++i)
				if(!v[*i])
					DFS(g,*i,n,v);
}
void rez(int vf,int ctc)
{
	memset(v1,0,sizeof(v1));
	memset(v2,0,sizeof(v2));
	DFS(G1,vf,n,v1);
	DFS(G2,vf,n,v2);
	for(int i=1;i<=n;i++)
		if(v1[i]==v2[i]&&v1[i]!=0)
			c[i]=ctc;
}

int main()
{
	citire();
	int nrc=0;
	for(int i=1;i<=n;i++)
		if(c[i]==0)
		{
			++nrc;
			rez(i,nrc);
		}
		out<<nrc<<'\n';
		for(int i=1;i<=nrc;i++)
		{
			for(int j=1;j<=n;j++)
				if(c[j]==i)
					out<<j<<" ";
				out<<'\n';
		}
		return 0;
}