Cod sursa(job #948516)

Utilizator dudutCancel Radu Constantin dudut Data 10 mai 2013 19:13:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<iostream>
#include<cstdio>
#include <algorithm> 
#include<vector>
using namespace std;

int a[100][100],k;
int index[100],leg[100],n,m,ind = 1;

vector <int> vec;
vector <int> vec2;
bool compar (int i,int j) { return (i>j); }

int min ( int a, int b) {
	if ( a > b )
		return b;
	return a;
}

void tareconex (int v);

void tarjan () {
	int i;
	for ( i = 1; i <= n; i++)
		if ( index[i] == 0 ){
			tareconex(i);
		}
}

void tareconex( int v ) {
	index[v] = ind;
	leg[v] = ind;
	ind++;
	vec.push_back(v);
	int i,j;
	
	for ( i = 1; i <= n; i++) {
		if ( a[v][i] == 1 ) {
			if ( index[i] == 0 ) {
				tareconex(i);
				leg[v] = min (leg[i], leg[v]);
			}
			else
				for ( j = 0; j < vec.size(); j++)
					if( i == vec[j])
						leg[v] = min (leg[v], index[i]);
		}
	}
	
	int x;
	if ( leg[v] == index[v] ){

		do {
			x = vec.back();
			vec.pop_back();
			vec2.push_back(x);
			
		}
		while ( x != v) ;
		
		sort(vec2.begin(), vec2.end(), compar);
		while(!vec2.empty()) {
			x = vec2.back();
			vec2.pop_back();
			printf("%d ",x);
		}
		printf("\n");
		k++;
	}
}

int main() {
	freopen ("ctc.in","r",stdin);
	freopen ("ctc.out","w",stdout);
	
	int i,x,y;
	scanf("%d%d", &n, &m);
	
	for ( i = 1; i <= m; i++) {
		scanf("%d%d", &x,&y);
		a[x][y] = 1;
	}
	tarjan();
	cout<<k;
	return 0;
}