poj1523解题报告

题意就是要求割点

用tarjan求强连通

#include <iostream>
#include <cstring>
using namespace std ;

const int MAXN = 1100 ; 
const int MAXM = MAXN * MAXN ; 

struct type
{
	int  to , next ; 
} ; 

type  edge[MAXM] ; 
int   head[MAXN] , Count , low[MAXN] , dfn[MAXN] , stack[MAXN] , top , ans[MAXN] , vis[MAXN] , son ; 

void  addedge( int start , int end )
{
	edge[Count].to = end ; 
	edge[Count].next = head[start] ; 
	head[start] = Count ++ ; 
}

void  tarjan_dfs( int cur , int father , int &cnt , int &Time )
{
	dfn[cur] = low[cur] = Time ++ ;
	vis[cur] = 1 ; 
	for( int i = head[cur] ; i != -1 ; i = edge[i].next )
	{
		int  v = edge[i].to ;
		if( v == father ) continue ;
		if( !vis[v] )
		{
			tarjan_dfs( v , cur , cnt , Time ) ; 
			low[cur] = min( low[cur] , low[v] ) ;
			if( dfn[cur] <= low[v] )
			{
				ans[cur] ++ ;
			}
		}
		else low[cur] = min( low[cur] , dfn[v] ) ;
	}
}

int   tarjan( int n )
{
	int   Time = 0 , cnt = 0 ;
	top = 0 ; 
	memset( dfn , 0 , sizeof( dfn ) ) ; 
	memset( low , 0 , sizeof( low ) ) ;
	memset( vis , 0 , sizeof( vis ) ) ; 

			tarjan_dfs( 1 , -1 , cnt , Time ) ; 
	return cnt ; 
}

int main()
{
	int  start , end , Max , cnt = 1 ; 
	while( 1 )
	{
		memset( head , -1 , sizeof( head ) ) ;
		Count = 0 ;
		int  flag = 0 ;
		Max = 0 ;
		while( cin >> start ){
			if( start ) flag = 1 ;
			if( !start ) break ;
			cin >> end ;
			if( start > Max ) Max = start ;
			if( end > Max ) Max = end ;
			addedge( start , end ) ;
			addedge( end , start ) ;
		}
		if( !flag ) break ;
		son = 0 ; 
		for( int i = 2 ; i <= Max ; i ++ ) ans[i] = 1 ; 
		ans[1] = 0 ; 
		tarjan( Max ) ;
		cout << "Network #" << cnt << endl ;
		cnt ++ ;
		flag = 0 ;
		for( int i = 1 ; i <= Max ; i ++ ){
			if( ans[i] > 1 ){
				cout << "  SPF node " << i << " leaves " << ans[i] << " subnets" << endl ;
				flag = 1 ;
			}
		}
		if( !flag ) cout << "  No SPF nodes" << endl ;
		cout << endl ; 
	}
	return 0 ; 
}