3177.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3177  User Id:fzk 
Memory:120K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

struct edge {
	int to;
	edge *next;
	bool key;
}e[21001];

int en = 0; 
edge *e_begin[5001];
edge *e_end[5001];

int to[5001];
bool sign[5001];
int n;
int f[5001];
int st[5001], sn;

int find( int k ) {
	sn = 0;
	while( f[k] >= 0 ) {
		st[sn++] = k;
		k = f[k];
	}
	while( sn-- )
		f[ st[sn] ] = k;
	return k;
}

void merge( int a, int b ) {
	if( a != b ) {
		if( f[a] == f[b] ) {
			f[b] = a;
			e_end[a]->next = e_begin[b];
			e_end[a] = e_end[b];
			f[a]--;
		}
		else if( f[a] < f[b] ) {
			f[b] = a;
			e_end[a]->next = e_begin[b];
			e_end[a] = e_end[b];
		}
		else {
			f[a] = b;
			e_end[b]->next = e_begin[a];
			e_end[b] = e_end[a];
		}
	}
}


void init( ) {
	int m, a, b, i;
	
	scanf( "%d%d", &n, &m );

	for( i=0; i<n; i++ ) {
		to[i] = i;
		e_begin[i] = e_end[i] = 0;
	}

	while( m-- ) {
		scanf( "%d%d", &a, &b );
		a--; b--;

		e[en].to = b<<16 | m ;
		e[en].next = e_begin[a];
		e[en].key = false;
		e_begin[a] = &e[en];
		if( e_end[a] == 0 )
			e_end[a] = &e[en];
		en++;

		e[en].to = a<<16 | m ;
		e[en].next = e_begin[b];
		e[en].key = false;
		e_begin[b] = &e[en];
		if( e_end[b] == 0 )
			e_end[b] = &e[en];
		en++;
	}

	memset( f, -1, sizeof f );
}

int search( int k, int id ) {
	int t, idt, r;
	edge temp;

	sign[k] = true;
	k = find( k );

	for( edge *p = e_begin[k]; p; p = p->next ) 
	if( !p->key ) {
		p->key = true;
		idt = p->to & (1<<16)-1;

		if( idt != id ) {

			t = find( p->to >> 16 );

			if( t != k ) {
				if( sign[t] ) {
					merge( k, t );
					return t;
				}
				else {
					r = search( t, idt );
					if( r == k ) {
						k = find( k );
						temp.next = e_begin[k];
						p = &temp;
					}
					else if( r != -1 ) {
						merge( k, find(r) );
						return r;
					}
				}
			}
		}
	}

	return -1;
}

int leaves = 0;
int max_d = 0;

void search1( int k, int f ) {
	int j, d = 0;

	sign[k] = true;
	
	for( edge *p=e_begin[k]; p; p=p->next ) {
		j = find( p->to>>16 );
		if( j != f && !sign[ j ] ) {
			d++;
			search1( j, k );
		}
	}

	if( d == 0 || ( d == 1 && f == -1 ) )
		leaves++;

	if( f != -1 && d+1 > max_d )
		max_d = d+1;
	if( f == -1 && d > max_d )
		max_d = d;
	
}

int main( ) {
	int ans;

	init( );

	memset( sign, 0, sizeof sign );
	search( 0, -1 );
	memset( sign, 0, sizeof sign );
	search1( find(0), -1 );

	if( leaves == 1 )
		ans = 0;
	else
		ans = (leaves+1)/2;

	printf( "%d\n", ans );

	return 0;
}