Cod sursa(job #1021232)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 3 noiembrie 2013 15:44:23
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <iostream>
using namespace std;

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

#include <vector>
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define LE 200666
//#define cout g

bool viz2[LE],viz[LE],st[LE];
int n,m,i,nrc,level[LE];
vector<int> H[LE],result[LE];
int up_max[LE],k,A[LE];

void dfs(int nod,int lev)
{
	level[nod]=lev;
	int N=H[nod].size(),i;
	up_max[nod]=lev;
	viz[nod]=true;
	A[++k]=nod;
	
	for(i=0;i<N;++i)
	{
		if (viz[H[nod][i]]==false)
		{
			dfs(H[nod][i],lev+1);
		    up_max[nod]=min(up_max[nod],up_max[H[nod][i]]);
		}
		
		if (st[H[nod][i]]==false) up_max[nod]=min(up_max[nod],up_max[H[nod][i]]);
	}
    
	if (up_max[nod]==level[nod])
	{
		++nrc;
		while (k>0)
		{
			st[A[i]]=true;
			result[nrc].pb(A[k]);
			if (A[k]==nod) {--k;break;}
			--k;
        }
	}
}


int main()
{
	f>>n>>m;
	
	for(i=1;i<=m;++i)
	{
		int xx,yy;
		f>>xx>>yy;
		H[xx].pb(yy);
	}
	
	for(i=1;i<=n;++i) 
		if (viz[i]==false)
			dfs(i,1);
	
	for(i=1;i<=n;++i) viz[i]=false;
		
	cout<<nrc<<'\n';
	
	for(i=1;i<=nrc;++i)
	{
		int N=result[i].size();
		for(int j=0;j<N;++j) cout<<result[i][j]<<" ";
		cout<<'\n';
	}
		
	return 0;
}