Cod sursa(job #2105817)

Utilizator anderut22Sandu Andrei anderut22 Data 14 ianuarie 2018 13:01:28
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <vector>
#define NMAX 100001
#define MMAX 5000
using namespace std;
FILE *fin=fopen("ctc.in", "r");
FILE *fout=fopen("ctc.out", "w");

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

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

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

void citire()
{
	int i, a, b;
	fscanf(fin, "%d %d", &n, &m);
	for (i=1; i<=m; i++)
	{
		fscanf(fin, "%d %d", &a, &b);
		la[a].push_back(b);
		lat[b].push_back(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]);
		}
	}
	fprintf(fout, "%d\n", nctc);
	for (i=1; i<=nctc; i++)
	{
		for (j=1; j<=n; j++) if (ctc[j]==i) fprintf(fout, "%d ", j);
		fprintf(fout, "\n");
	}
}

void DFS1(int k)
{
	int i;
	vizitat[k]=1;
	for (i=0; i<la[k].size(); 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=0; i<lat[k].size(); i++)
	{
		if (!scris[lat[k][i]]) DFS2(lat[k][i]);
	}
}