Cod sursa(job #3041006)

Utilizator 222cezarCezar Stilpeanu 222cezar Data 30 martie 2023 19:34:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE "ctc"

ifstream in(FILE".in");
ofstream out(FILE".out");


#define M 100100
#define N 100100

struct el {
	int vf, urm;
};

el g_s[2 * M], g_p[2 * M], ctc[N];
int lst_s[N], lst_p[N], g_s_topo[N], lst_c[N], c[N];
int n, n_s_top, m, nrs, nrp, nrc, n_c;
bool viz[N];



void adauga(int u, int v, el g[], int lst[], int &nr) {
	nr++;
	g[nr].vf = v;
	g[nr].urm = lst[u];
	lst[u] = nr;
}

//parcurgere for(int p = lst[u]; p != 0; p = v[p].urm) { int v = v[p].vf; }

void dfs_ini(int u)
{
	viz[u] = 1;
	for(int p=lst_s[u]; p!=0; p=g_s[p].urm)
	{
		int v = g_s[p].vf;
		if(!viz[v])
			dfs_ini(v);
	}
	g_s_topo[++n_s_top] = u;
}

void dfs_trans(int u)
{
	c[u] = n_c;
	for(int p=lst_p[u]; p!=0; p=g_p[p].urm)
	{
		int v = g_p[p].vf;
		if(c[v] == 0)
			dfs_trans(v);
	}
}

int main()
{
	in >> n >> m;

	for(int i=0; i<m; i++)
	{
		int u, v;
		in >> u >> v;
		adauga(u, v, g_s, lst_s, nrs);
		adauga(v, u, g_p, lst_p, nrp);
	}

	in.close();

	for(int i=1; i<=n; i++)
		if(!viz[i])
			dfs_ini(i);

	for(int i=n_s_top; i>=1; i--)
		if(c[g_s_topo[i]] == 0)
		{
			n_c++;
			dfs_trans(g_s_topo[i]);
		}

	out << n_c << '\n';

	for(int i=n; i>=1; i--)
	{
		adauga(c[i], i, ctc, lst_c, nrc); //il adaug pe i in lista c[i]
	}
	for(int i=1; i<=n_c; i++)
	{
		for(int p=lst_c[i]; p!=0; p=ctc[p].urm)
		{
			int u = ctc[p].vf;
			out << u << " ";
		}
		out << '\n';
	}
	out.close();
}