Cod sursa(job #904337)

Utilizator crushackPopescu Silviu crushack Data 4 martie 2013 09:49:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define NMax 100010
using namespace std;

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

int N,M;
int T[NMax],idx[NMax];
bool in_stack[NMax];
vector<int> ad[NMax];
stack<int> st;
vector<vector<int> > Sol;

void tarjan(int x,int lv=0){

	int i;
	static int index;
	T[x]=idx[x]=++index;
	st.push(x);
	in_stack[x]=true;
	for (i=0;i<(int)ad[x].size();++i) if (!idx[ad[x][i]])
			tarjan(ad[x][i]),
			T[x]=min(T[x],T[ad[x][i]]);
		else if (in_stack[ad[x][i]])
			T[x]=min(T[x],T[ad[x][i]]);

	if (idx[x]==T[x]){
		vector<int> vec;
		for (i=-1;i!=x;){
			i=st.top();st.pop();
			vec.push_back(i);
			in_stack[i]=false;
		}
		Sol.push_back(vec);
	}

}

int main()
{
	int i,j,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);

	tarjan(1);

	freopen(OUT,"w",stdout);
	printf("%d\n",Sol.size());
	for (i=0;i<(int)Sol.size();++i,printf("\n"))
	{
		sort(Sol[i].begin(),Sol[i].end());
		for (j=0;j<(int)Sol[i].size();++j)
			printf("%d ",Sol[i][j]);
	}
	fclose(stdout);
	return 0;
}