Cod sursa(job #578035)

Utilizator keenoxCoriu Radu Gabriel - UPB keenox Data 10 aprilie 2011 21:54:47
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

bool **graf;
int N,M;
vector<int> S;
int *idx, *lowlink;
vector<vector<int> > componente;
vector<int> cmp;

void tarjan(int v)
{
	static int index = -1;
	int tmp;

	index++;
	idx[v] = lowlink[v] = index;
	S.push_back(v);

	for (int j=0;j<N;j++)
	if (graf[v][j])
	{
		if (idx[j] == -1)
		{
			tarjan(j);
			lowlink[v] = min(lowlink[j], lowlink[v]);
		}
		else if( find(S.begin(),S.end(),lowlink[j]) != S.end() )
				lowlink[v] = min(lowlink[j], 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);
		if (cmp.size()>1)
			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*));


	for (int i=0;i<N;i++)
	{
		graf[i] = (bool*)malloc(N*sizeof(bool));
		idx[i] = -1;
	}

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

	fclose(fin);

	ctc_tarjan();

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