Cod sursa(job #2434546)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 2 iulie 2019 11:57:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
const int NMAX=1e5+5;
int n,m,x,y,viz1[NMAX],viz2[NMAX],ord[NMAX],nr,cnt;
vector <int> g[NMAX],invg[NMAX],comp[NMAX];
void dfs1(int x)
{
	viz1[x]=1;
	for(auto y:invg[x])
		if(!viz1[y])
			dfs1(y);
	ord[++cnt]=x;
}
void dfs2(int x)
{
	viz2[x]=nr;
	comp[nr].push_back(x);
	for(auto y:g[x])
		if(!viz2[y]) dfs2(y); 
}
int main()
{
	fi>>n>>m;
	for(int i=1;i<=m;i++)
	{
		fi>>x>>y;
		g[x].push_back(y);
		invg[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		if(!viz1[i]) dfs1(i);
	for(int i=n;i>=1;i--)
		if(!viz2[ord[i]]) 
		{
			nr++;
			dfs2(ord[i]);
		}
	fo<<nr<<"\n";
	for(int i=1;i<=n;i++)
	{
		for(auto x:comp[i])
			fo<<x<<" ";
		fo<<"\n";
	}
	fi.close();
	fo.close();
	return 0;
}