Cod sursa(job #1902962)

Utilizator Firealex2Rotileanu Alexandru Firealex2 Data 4 martie 2017 21:20:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

ifstream fi("ctc.in");
ofstream fo("ctc.out");


void dfsa(int x);
void dfsb(int x);
void solve();
void citire();
void afisare();

int N, M, nrc, st[100001], l, t;
bool viza[100001], vizb[100001];
vector<int> muchiia[100001];
vector<int> muchiib[100001];
vector<int> ctc[100001];


int main()
{
	citire();
	solve();
	afisare();
	return 0;
}

void citire()
{
	fi >> N >> M;
	for (int i = 1;i <= M;i++)
	{
		int x, y;
		fi >> x >> y;
		muchiia[x].push_back(y);
		muchiib[y].push_back(x);
	}

	return;
}

void solve()
{
	for (int i = 1;i <= N;i++)
		if (!viza[i])
			dfsa(i);
	for (int i = N;i >= 1;i--)
	{
		if (!vizb[st[i]])
		{
			nrc++;
			dfsb(st[i]);
		}
	}
	return;
}

void dfsa(int x)
{
	viza[x] = true;
	for (int i = 0;i < muchiia[x].size();i++)
		if(!viza[muchiia[x][i]])
			dfsa(muchiia[x][i]);
	st[++l] = x;
	return;
}

void dfsb(int x)
{
	ctc[nrc].push_back(x);
	vizb[x] = true;
	for (int i = 0;i < muchiib[x].size();i++)
		if (!vizb[muchiib[x][i]])
			dfsb(muchiib[x][i]);
	return;
}

void afisare()
{
	fo << nrc << '\n';
	for (int i = 1;i <= nrc;i++)
	{
		for (int j = 0;j < ctc[i].size();j++)
			fo << ctc[i][j] << ' ';
		fo << '\n';
	}
	return;
}