Cod sursa(job #2868117)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 10 martie 2022 18:59:34
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <algorithm>
#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;
	comptcon[nctc].push_back(x);
	for (int i = 0; i < rG[x].size(); i++)
		if (ctc[rG[x][i]] == 0)
			dfs2(rG[x][i]);
}
bool comp (vector <int> a, vector <int> b)
{
    return a[0] < b[0];
}
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);
    comptcon.resize(1);
	for (i = n - 1; i >= 0; i--)
		if (ctc[order[i]] == 0)
		{
			nctc++;
			vector <int> k;
			comptcon.push_back(k);
			dfs2(order[i]);
			sort (comptcon[nctc].begin(), comptcon[nctc].end());
		}
    sort (comptcon.begin()+1, comptcon.end(), comp);
	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;
}