Cod sursa(job #282317)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 17 martie 2009 13:37:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN  "ctc.in"
#define OUT "ctc.out"
#define N_MAX 1<<17

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;

int rez(-1),N,M,indx(1);
vector<bool> in_stack(N_MAX);
int ind[N_MAX],lowind[N_MAX],con;
vector<VI> A(N_MAX),C(N_MAX);
stack<int> S;

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d %d\n",&N,&M); 
	
	int x,y;
	FOR(i,1,M)
	{
		scanf("%d %d\n",&x,&y);
		A[x].pb(y);
	}	
}

II void Tarjan(int nod)
{
	in_stack[nod] = true;
	ind[nod] = lowind[nod] = indx++;
	
	S.push(nod);
	
	for(int i=0;i<(int)A[nod].sz();++i)
	{
		int fiu = A[nod][i];
		if(ind[fiu] && !in_stack[fiu])
			continue;
		if(!ind[fiu])
			Tarjan(fiu);
		lowind[nod] = min(lowind[nod],lowind[fiu]);
	}
	
	if(ind[nod] == lowind[nod])
	{
		++rez;
		for(int fiu = 0;fiu != nod;C[rez].pb(fiu = S.top() ),S.pop(),in_stack[fiu] = false);
	}
}

II void solve()
{
	FOR(i,1,N)
		if(!ind[i])
			Tarjan(i);
	
	printf("%d\n",rez+1);
	FOR(i,0,rez)
	{
		for(int j=0;j<(int)C[i].sz();++j)
			printf("%d ",C[i][j]);
		printf("\n");
	}	
}

int main()
{
	scan();
	solve();
	return 0;
}