Cod sursa(job #715441)

Utilizator noobakafloFlorin eu noobakaflo Data 17 martie 2012 11:35:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

#define MAX_N 100001

int n,m,vizitat[MAX_N];
vector<int> g[MAX_N],gt[MAX_N],subgraf_max,st;
vector< vector<int> > solutie;


void citeste_graf(void)
{
	freopen("ctc.in","r",stdin);
	int i,x,y;
	scanf("%d %d",&n,&m);
	for(i=1; i<=m; i++)
	{
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		gt[y].push_back(x); //formez graful transpus
	}
	fclose(stdin);
}

void DF1(int nod)
{
	vector<int> ::iterator i;
	
	vizitat[nod]=1;
	for(i=g[nod].begin(); i!=g[nod].end(); i++)
		if(!vizitat[*i])
			DF1(*i);
	st.push_back(nod);
}

void DF2(int nod)
{
	vector<int> ::iterator i;
	
	vizitat[nod]=1;
	for(i=gt[nod].begin(); i!=gt[nod].end(); i++)
		if(!vizitat[*i])
			DF2(*i);
	subgraf_max.push_back(nod);
}

void sortare_topologica(void)
{
	int i;
	for(i=1; i<=n; i++)
		if(!vizitat[i])
			DF1(i);
}

void componente_tare_conexe(void)
{
	sortare_topologica();
	vector<int> ::iterator i;
	memset(vizitat,0,sizeof(vizitat));
	for(i=st.end()-1; i>=st.begin(); i--)
		if(!vizitat[*i])
		{
			DF2(*i);
			solutie.push_back(subgraf_max);
			subgraf_max.clear();
		}
}

void afiseaza_solutie(void)
{
	freopen("ctc.out","w",stdout);
	vector< vector<int> > ::iterator i;
	vector<int> ::iterator j;
	printf("%d\n",solutie.size());
	for(i=solutie.begin(); i!=solutie.end(); i++)
	{
		for(j=(*i).begin(); j!=(*i).end(); j++)
			printf("%d ",*j);
		printf("\n");
	}
	fclose(stdout);
}
	

int main()
{
	citeste_graf();
	componente_tare_conexe();
	afiseaza_solutie();
	return 0;
}