Cod sursa(job #2481035)

Utilizator _Tudor_Tudor C _Tudor_ Data 26 octombrie 2019 13:06:43
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <map>
using namespace std;

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

const int NMax = 80000;

int n, m;
vector<int> g[NMax + 5];
vector<int> gtr[NMax + 5];
vector<int> ctc[NMax + 5];
int nrctc;
int comp[NMax + 5];
int use[NMax + 5];

void resetUse()
{
	for(int i = 1; i <= n; i++)
		use[i] = 0;
}

void read()
{
	fin >> n >> m;

	int x, y;
	for (int i = 0; i < m; i++)
	{
		fin >> x >> y;
		g[x].push_back(y);
		gtr[y].push_back(x);
	}
}

void DFS(int x, vector<int> graf[], int pas)
{
	use[x]++;
	if(use[x] == 2)
		ctc[nrctc].push_back(x);

	for (int i = 0; i < graf[x].size(); i++)
	{
		int vecin = graf[x][i];

		if(use[vecin] == pas - 1)
			DFS(vecin, graf, pas);
	}
}



int main()
{
	read();
	int k = 1;

	for (int i = 1; i <= n; i++)
	{
		if (comp[i] == 0)
		{
            nrctc++;
			DFS(i, g, 1);
			DFS(i, gtr, 2);

			for(int i = 1; i <= n; i++)
				if(use[i] == 2)
					comp[i] = k;

			resetUse();
			k++;
		}
	}

	fout << nrctc << '\n';
	for (int i = 1; i <= nrctc; i++)
	{
		for(int j = 0; j < ctc[i].size(); j++)
			fout << ctc[i][j] << ' ';
		fout << '\n';
	}
}