Cod sursa(job #2676310)

Utilizator Cosma05Cosma Tudor Cosma05 Data 23 noiembrie 2020 22:20:52
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define NMax 100005

vector<int>G[NMax], H[NMax];
stack<int> S;

vector<int>rez[NMax];

int n, m,beenThere[NMax],nrCTC;

void read()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		H[y].push_back(x);
	}
}

void dfs(int x)
{
	beenThere[x] = 1;
	//zona 1 = zona cand a fost descoperit nodul
	for (unsigned int i=0;i<G[x].size();i++)
	{	//zona 2
		int vecin=G[x][i];
		if(!beenThere[vecin])
            dfs(vecin);
			//zona 3
	}
	S.push(x);
	//zona 4 = zona in care se gata toti vecinii de vizitat a nodului curent pentru care s-a fct dfs
}

void dfsGT(int x)
{
	beenThere[x] = 2;
	rez[nrCTC].push_back(x);

	for (unsigned int i=0;i<H[x].size();i++)
		{
		    int vecin=H[x][i];
		    if(beenThere[vecin]==1)
                dfsGT(vecin);
		}
}

void solve()
{
	for (int i = 1; i <= n; i++)
		if (!beenThere[i])
			dfs(i);

	while (!S.empty())
	{
		int k = S.top();
		if (beenThere[k] == 1)
		{
			nrCTC++;
			dfsGT(k);
		}
		S.pop();
	}
}

void print()
{
    for(int i=1;i<=n;i++)
        sort(rez[i].begin(),rez[i].end());
	fout << nrCTC << endl;
	for (int i = 1; i <= nrCTC; i++)
	{
		for (unsigned int j = 0; j < rez[i].size(); j++) fout << rez[i][j] << " ";
		fout << endl;
	}
}

int main()
{
	read();
	solve();
	print();
	return 0;
}