Cod sursa(job #2868125)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 10 martie 2022 19:02:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, j, x, y, nctc;
vector <vector <int>> G, rG, comptcon;
vector <int> viz, ctc, order;
void dfs1(int x)
{
	viz[x] = 1;
	for (int i = 0; i < G[x].size(); i++)
		if (viz[G[x][i]] == 0)
			dfs1(G[x][i]);
	order.push_back(x);
}
void dfs2(int x)
{
	ctc[x] = nctc;
	for (int i = 0; i < rG[x].size(); i++)
		if (ctc[rG[x][i]] == 0)
			dfs2(rG[x][i]);
}
int main()
{
	fin >> n >> m; G.resize(n + 1), rG.resize(n + 1), viz.resize(n + 1), ctc.resize(n + 1);
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		G[x].push_back(y);
		rG[y].push_back(x);
	}
	for (i = 1; i <= n; i++)
		if (viz[i] == 0)
			dfs1(i);
	for (i = n - 1; i >= 0; i--)
		if (ctc[order[i]] == 0)
		{
			nctc++;
			dfs2(order[i]);
		}
    comptcon.resize(nctc+1);
    for (i = 1; i <= n; i++)
        comptcon[ctc[i]].push_back(i);
    fout << nctc << '\n';
    for (i = 1; i <= nctc; i++)
    {
        for (j = 0; j < comptcon[i].size(); j++)
            fout << comptcon[i][j] << ' ';
        fout << '\n';
    }
	return 0;
}