Cod sursa(job #2097011)

Utilizator ghost24ghost ghost ghost24 Data 30 decembrie 2017 12:48:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define DN 100010

using namespace std;
fstream fin("ctc.in", ios::in), fout("ctc.out", ios::out);
vector<int> v1[DN], v2[DN], r[DN];
stack<int> st;
int n,m,ap[DN],nrc=0;
void dfs1(int n);
void dfs2(int n);
int main()
{
	int i,x,y;
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		v1[x].push_back(y);
		v2[y].push_back(x);
	}
	for(i=1;i<=n;i++)
		if(ap[i]==0)
			dfs1(i);
	for(i=1;i<=n;i++) ap[i]=0;
	while( st.empty() == 0 )
	{
		i=st.top(); st.pop();
		if(ap[i]==0)
		{
			nrc++;
			dfs2(i);
		}
	}	
	fout<<nrc<<"\n";
	for(i=1;i<=nrc;i++)
	{
		for( auto x:r[i]) fout<<x<<" ";
		fout<<"\n";
	}
}
void dfs1(int n)
{
	ap[n]=1;
	for( auto x:v1[n])
	{
		if(ap[x]==0) dfs1(x);
	}
	st.push(n);
}
void dfs2(int n)
{
	ap[n]=1;
	r[nrc].push_back(n);
	for( auto x:v2[n])
	{
		if(ap[x]==0)
		{
			dfs2(x);
		}
	}
}