Cod sursa(job #578078)

Utilizator keenoxCoriu Radu Gabriel - UPB keenox Data 10 aprilie 2011 22:40:27
Problema Componente tare conexe Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

vector<vector<int> > graf;
int N,M;
vector<int> S;
int *idx, *lowlink;
vector<vector<int> > componente;
vector<int> cmp;
int indexx = -1;

void tarjan(int v)
{
	int tmp;
	indexx++;
	idx[v] = lowlink[v] = indexx;
	S.push_back(v);

	for (vector<int>::iterator it=graf[v].begin(); it<graf[v].end(); it++)
	{
		if (idx[*it] == -1)
		{
			tarjan(*it);
			lowlink[v] = min(lowlink[*it], lowlink[v]);
		}
		else if( find(S.begin(),S.end(),lowlink[*it]) != S.end() )
				lowlink[v] = min(lowlink[*it], lowlink[v]);
	}

	if (lowlink[v] == idx[v])
	{
		// este v radacina unei CTC?
		//puts("O noua CTC: ");
		cmp.clear();
		do
		{
			tmp = S.back();
			S.pop_back();
			//printf("%d ",tmp+1);
			cmp.push_back(tmp+1);
		}
		while (tmp != v);
		componente.push_back(cmp);
		//putchar('\n');
	}
}

void ctc_tarjan()
{
	for (int i=0;i<N;i++)
		if (idx[i] == -1) // nu a fost vizitat
			tarjan(i);
}

int main(int argc, char *argv[])
{
	int start,end;

	char filename[256] = "ctc.in";

	if (argc>1)
	{
		strcpy(filename,argv[1]);
	}

	FILE* fin = fopen(filename,"r");
	fscanf(fin,"%d%d",&N,&M);

	idx = (int*)malloc(N*sizeof(int));
	lowlink = (int*)malloc(N*sizeof(int));
	//graf = (bool**)malloc(N*sizeof(bool*));
	graf.resize(N);

	for (int i=0;i<N;i++)
		idx[i] = -1;

	for (int i=0;i<M;i++)
	{
		fscanf(fin,"%d%d",&start,&end);
		start--;end--;
		graf[start].push_back(end);
	}

	fclose(fin);

	ctc_tarjan();

	FILE* fout = fopen("ctc.out","w");
	fprintf(fout,"%d\n",componente.size());
	for (unsigned int i=0;i<componente.size();i++)
	{
		for (unsigned int j=0;j<componente[i].size();j++)
			fprintf(fout,"%d ",componente[i][j]);
		fprintf(fout,"\n");
	}
	fclose(fout);
	return 0;
}