Cod sursa(job #2928907)

Utilizator RaduIonescuRadu Ionescu RaduIonescu Data 24 octombrie 2022 08:33:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
#include<vector>
#define MaxN 200005

using namespace std;

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

vector<int>G[MaxN],Gt[MaxN],sol[MaxN];
int post[MaxN],viz[MaxN],n,m,k,nr;

void dfs(int i)
{	vector<int>::iterator it;
	viz[i]=1;
	for(it=G[i].begin();it!=G[i].end();++it)
		if(!viz[*it])
			dfs(*it);
	post[++nr]=i;
}

void dfsm(int i)
{	vector<int>::iterator it;
	viz[i]=0;
	sol[k].push_back(i);
	for(it=Gt[i].begin();it!=Gt[i].end();++it)
		if(viz[*it])
			dfsm(*it);
}

int main()
{	int i,x,y;
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{	fin>>x>>y;
		G[x].push_back(y);
		Gt[y].push_back(x);
	}
	for(i=1;i<=n;i++)
		if(!viz[i])
			dfs(i);
	for(i=n;i>0;i--)
		if(viz[post[i]])
		{	k++;
			dfsm(post[i]);
		}
	fout<<k<<'\n';
	vector<int>::iterator it;
	for(i=1;i<=k;i++)
	{	for(it=sol[i].begin();it!=sol[i].end();it++)
			fout<<*it<<' ';
		fout<<'\n';
	}
	return 0;
}