Cod sursa(job #2928904)

Utilizator RaduIonescuRadu Ionescu RaduIonescu Data 24 octombrie 2022 08:09:43
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
#include<vector>

using namespace std;

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

vector<int> ad_list[200005],anti_ad_list[200005],comp[200005];
int v[200005],viz[200005],n,m,k,nr,nr_comp;

void dfs(int nod)
{
	viz[nod]=1;

	for(int i = 0; i < ad_list[nod].size(); i++)
		if(!viz[ad_list[nod][i]])
			dfs(ad_list[nod][i]);

	v[nr++] = nod;
}

void anti_dfs(int nod)
{
	viz[nod]=0;

	comp[k].push_back(nod);

	for(int i = 0; i < anti_ad_list[nod].size(); i++)
		if(viz[anti_ad_list[nod][i]])
			anti_dfs(anti_ad_list[nod][i]);
}

int main()
{	int i,x,y;

	in>>n>>m;

	for(int i = 1; i <= m; i++)
	{
	    in>>x>>y;

		ad_list[x].push_back(y);

		anti_ad_list[y].push_back(x);
	}

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

	for(int i = n; i > 0; i--)
		if(viz[v[i]])
		{
		    k++;

			anti_dfs(v[i]);
		}

	out<<nr_comp<<"\n";

	for(int i = 1;i <= nr_comp;i ++)
	{
	    for(int j = 0; j < comp[i].size(); j++)    out<<comp[i][j]<<"\n";

		out<<"\n";
	}

	return 0;
}