Cod sursa(job #760418)

Utilizator crushackPopescu Silviu crushack Data 21 iunie 2012 11:56:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define NMax 100010
using namespace std;

const char IN[]="ctc.in",OUT[]="ctc.out";

int N,M,index;
int T[NMax],t[NMax];
bool b[NMax] , inSt[NMax];
vector<int> ad[NMax] ;
stack<int> st;
vector<vector<int> > Sol;

void tarjan(int x)
{
	b[x]=true;
	inSt[x]=true;st.push(x);
	t[x]=T[x]=++index;
	
	for (int i=0;i<(int)ad[x].size();++i) if (!b[ad[x][i]])
	{
		tarjan(ad[x][i]);
		T[x]=min(T[x],T[ad[x][i]]);
	}
	else if (inSt[ad[x][i]]) T[x]=min(T[x],T[ad[x][i]]);
	
	if (T[x]==t[x])
	{
		vector<int> vec;
		while (st.top()!=x)
		{
			vec.push_back(st.top());
			inSt[st.top()]=false;
			st.pop();
		}
		vec.push_back(st.top());
		inSt[st.top()]=false;
		st.pop();
		
		Sol.push_back(vec);
	}
	
}

int main()
{
	int x,y;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	while (M--)
	{
		scanf("%d%d",&x,&y);
		ad[x].push_back(y);
	}
	fclose(stdin);
	
	for (int i=1;i<=N;++i) if (!b[i])
		tarjan(i);
	
	freopen(OUT,"w",stdout);
	printf("%d\n",Sol.size());
	for (int i=0;i<(int)Sol.size();++i,printf("\n"))
		for (int j=0;j<(int)Sol[i].size();++j)
			printf("%d ",Sol[i][j]);
	fclose(stdout);
	
	return 0;
}