Cod sursa(job #2142338)

Utilizator LoganCarlos Mensia Logan Data 24 februarie 2018 22:27:31
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream> // O(m)
#include <algorithm>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int>A[100001],B[100001],C[81000];
stack<int>stk;
vector<bool>P;
int n,m,k,x,y,i;
void defeu(int x)
{
	P[x]=1;
	for(auto i:A[x]) if(!P[i]) defeu(i);
	stk.push(x);
}
void defeu2(int x,int k)
{
	P[x]=1; C[k].push_back(x);
	for(auto i:B[x]) if(!P[i]) defeu2(i,k);
}
int main()
{
	cin>>n>>m;
	P.resize(n+1);
	while(m) cin>>x>>y,A[x].push_back(y),B[y].push_back(x),--m;
	for(i=1;i<=n;++i) if(!P[i]) defeu(i);
	P.assign(n+1,0);
	while (!stk.empty())
	{
		i=stk.top(); stk.pop();
		if(!P[i]) k++,defeu2(i,k);
	}
	cout<<k<<'\n';
	for(int i=1;i<=k;i++)
    {for(auto j:C[i]) cout<<j<<' '; cout<<'\n';}
}