Cod sursa(job #827104)

Utilizator zalmanDanci Emanuel Sebastian zalman Data 1 decembrie 2012 17:14:51
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 100
#define pb push_back
using namespace std;

int N, M, cnt;
vector<int> GD[NMAX], GT[NMAX], ind_comp, comp[NMAX];
stack<int> st;
bool viz[NMAX];

void read(void)
{
	int x, y;
	FILE *f = fopen("ctc.in", "r");
	
	fscanf(f, "%d%d", &N, &M);
	while(M--)
	{
		fscanf(f, "%d%d", &x, &y);
		GD[x].pb(y);
		GT[y].pb(x);
	}
	fclose(f);
}

void DFSGD(int nod)
{
	viz[nod] = 1;
	for(int i = 0; i < GD[nod].size(); ++i)
		if(!viz[GD[nod][i]])
			DFSGD(GD[nod][i]);
	st.push(nod);
}

void DFSGT(int nod, int indice)
{
	ind_comp[nod] = indice;
	for(int i = 0; i < GT[nod].size(); ++i)
		if(ind_comp[GT[nod][i]] == -1)
			DFSGT(GT[nod][i], indice);	
}
void solve(void)
{
	for(int i = 1; i <= N; ++i)
		if(!viz[i])
			DFSGD(i);
		
	ind_comp.resize(N);
	ind_comp.assign(ind_comp.size()+1, -1);
	
	for(; !st.empty(); st.pop())
	{
		int sttop = st.top();
		if(ind_comp[sttop] == -1)
		{
			++cnt;
			DFSGT(sttop, cnt);
		}
	}
	
	for(int i = 0; i < ind_comp.size(); ++i)
		comp[ind_comp[i]].push_back(i);		
}

void print(void)
{
	FILE *g = fopen("ctc.out", "w");
	
	fprintf(g, "%d\n", cnt);
	for(int i = 1; i <= N; ++i)
	{
		for(int j = 0; j < comp[i].size(); ++j)
			fprintf(g, "%d ", comp[i][j]);
		fprintf(g, "\n");
	}
	
	fclose(g);
}
int main(void)
{
	read();
	solve();
	print();
}

/*
printf("%d\n", cnt);
for(;!st.empty();printf("%d ", st.top()), st.pop());
	
for(int i = 1; i <= N; ++i)
	{
		printf("\n%d: ", i);
		for(int j = 0; j < G[i].size(); ++j)
			printf("%d ", G[i][j]);
	}
*/