Cod sursa(job #921602)

Utilizator cbanu96Banu Cristian cbanu96 Data 21 martie 2013 09:28:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

#define NMAX 100005
#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"

using namespace std;

vector<int> V[NMAX];
int idx[NMAX];
int lowlink[NMAX];
int in_st[NMAX];
vector<vector<int> > sol;
vector<int> ctc;
stack<int> st;
int indice;


inline int min(int a, int b)
{
	return a < b ? a : b;
}

void tarjan( int node )
{
	int i;
	idx[node] = indice;
	lowlink[node] = indice;
	indice++;
	st.push(node);
	in_st[node] = 1;
	for ( i = 0; i < V[node].size(); i++)
	{
		if(idx[V[node][i]] == -1)
		{
			tarjan(V[node][i]);
			lowlink[node] = min(lowlink[node], lowlink[V[node][i]]);
		}
		else
		if(in_st[V[node][i]] == 1)
		{
			lowlink[node] = min(lowlink[node], lowlink[V[node][i]]);
		}
	}
	if(idx[node] == lowlink[node])
	{
		ctc.clear();
		int tmp;
		do
		{
			tmp = st.top(), in_st[tmp] = 0, ctc.push_back(tmp);
			st.pop();
		}
		while(tmp != node);
		sol.push_back(ctc);
	}
}

int main()
{
	int n, m,i,j,x,y;
	freopen(FILEIN,"r",stdin);
	freopen(FILEOUT,"w",stdout);
	scanf("%d %d", &n, &m);
	for ( i = 1; i <= m; i++ )
	{
		scanf("%d %d", &x, &y);
		V[x].push_back(y);
	}
	for ( i = 1; i <= n; i++ )
		idx[i] = -1;
	for ( i = 1; i <= n; i++ )
		if(idx[i] == -1)
            tarjan(i);
	printf("%d\n",sol.size());
	for ( i = 0; i < sol.size(); i++)
	{
		for ( j = 0; j < sol[i].size(); j++)
			printf("%d ", sol[i][j]);
		printf("\n");
	}
	return 0;
}