Cod sursa(job #2549634)

Utilizator Iulia25Hosu Iulia Iulia25 Data 17 februarie 2020 21:05:32
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

const int N = 1e5 + 5;

struct Nod	{
	int et;
	Nod* adr;
} *L[N], *inv[N], *c[N];

int viz[N], ctc[N];
int x, y, n, m, k;

void PLUS(int start, int nod)	 {
	viz[nod] = k;
	for (Nod *a = L[nod]; a != NULL; a = a -> adr)	{
		if (viz[a -> et] != k)
			PLUS(start, a -> et);
	}
}

void MINUS(int start, int nod)	{
	if (viz[nod] == k)
		ctc[nod] = k;
	for (Nod *a = inv[nod]; a != NULL; a = a -> adr)	{
		if (!ctc[a -> et])
			MINUS(start, a -> et);
	}
}

int main()	{
  fin >> n >> m;
  for (int i = 1; i <= m; ++i)	{
		fin >> x >> y;
		Nod* p = new Nod;
		p -> et = y;
		p -> adr = L[x];
		L[x] = p;
		p = new Nod;
		p -> et = x;
		p -> adr = inv[y];
		inv[y] = p;
  }
  for (int i = 1; i <= n; ++i)	{
		if (!ctc[i])	{
			++k;
			PLUS(i, i);
			MINUS(i, i);
		}
  }
  for (int i = 1; i <= n; ++i)	{
		Nod *p = new Nod;
		p -> et = i;
		p -> adr = c[ctc[i]];
		c[ctc[i]] = p;
  }
  fout << k << '\n';
  for (int i = 1; i <= k; ++i)	{
		for (Nod *a = c[i]; a != NULL; a = a -> adr)	{
      fout << a -> et << ' ';
		}
		fout << '\n';
	}
}