Cod sursa(job #2105809)

Utilizator anderut22Sandu Andrei anderut22 Data 14 ianuarie 2018 12:37:38
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#define NMAX 1000
#define MMAX 5000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void citire();
void DFS1(int k);
void DFS2(int k);
void rulare();

int n, m, la[NMAX][NMAX], lat[NMAX][NMAX], postord[NMAX], ctc[NMAX], nctc;
bool vizitat[NMAX], scris[NMAX];

int main()
{
	citire();
	rulare();
	return 0;
}

void citire()
{
	int i, a, b;
	fin >> n>> m;
	for (i=1; i<=m; i++)
	{
		fin >> a>> b;
		la[a][0]++;
		la[a][la[a][0]]=b;
		lat[b][0]++;
		lat[b][lat[b][0]]=a;
	}
}

void rulare()
{
	int i, j;
	for (i=1; i<=n; i++)
	{
		if (!vizitat[i]) DFS1(i);
	}
	for (i=n; i>=1; i--)
	{
		if (!scris[postord[i]])
		{
			nctc++;
			DFS2(postord[i]);
		}
	}
	fout << nctc<< '\n';
	for (i=1; i<=nctc; i++)
	{
		for (j=1; j<=n; j++) if (ctc[j]==i) fout << j<< ' ';
		fout << '\n';
	}
}

void DFS1(int k)
{
	int i;
	vizitat[k]=1;
	for (i=1; i<=la[k][0]; i++)
	{
		if (!vizitat[la[k][i]]) DFS1(la[k][i]);
	}
	postord[0]++;
	postord[postord[0]]=k;
}

void DFS2(int k)
{
	int i;
	scris[k]=1;
	ctc[k]=nctc;
	for (i=1; i<=lat[k][0]; i++)
	{
		if (!scris[lat[k][i]]) DFS2(lat[k][i]);
	}
}