[UVa] 10199 - Tourist Guide

題目網址: http://goo.gl/HZMHHw

題意:
(from luckycat)


解法: 題目中所要求有照相機的地點，就是圖中的割點(Cut Vertex)。

TAG: Cut Vertex

注意:

程式碼:

	/**
	* Tittle: 10199 - Tourist Guide
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/11
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <map>
	#include <string>
	#include <algorithm>
	#include <vector>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	typedef map<string,int> MSI;
	typedef vector<string> VS;
	// declarations
	int mi = 0;
	int cm;
	int n, r;
	MSI n2i;
	string i2n[N];
	bool edge[N][N];
	VS cameras;
	// functions
	int vis[N], low[N];
	int dep;
	void dfs( int u, int pre )
	{
	bool cv = false;
	int son = 0;
	vis[u] = low[u] = ++dep;
	FOR( v, 1, n ) if( edge[u][v] && pre!=v ) {
	if( !vis[v] ) {
	++son;
	dfs( v, u );
	low[u] = min( low[u], low[v] );
	if( low[v] >= vis[u] )
	cv = true;
	} else
	low[u] = min( low[u], vis[v] );
	}
	if( (!pre && son>1) || (pre && cv) ) {
	++cm;
	cameras.push_back( i2n[u] );
	}
	}
	int cutVertex( void )
	{
	cm = 0;
	cameras.clear();
	clr( vis, 0 );
	dep = 0;
	FOR( i, 1, n ) if( !vis[i] )
	dfs( i, 0 );
	return cm;
	}
	// main function
	int main( void )
	{
	string su, sv;
	int u, v;
	// input
	while( scanf( "%d", &n )==1 && n ) {
	n2i.clear();
	FOR( i, 1, n ) {
	cin >> su;
	n2i[su] = i;
	i2n[i] = su;
	}
	scanf( "%d", &r );
	clr( edge, false );
	FOR( i, 1, r ) {
	cin >> su >> sv;
	u = n2i[su];
	v = n2i[sv];
	edge[u][v] = edge[v][u] = true;
	}
	// solve & output
	cutVertex();
	if( mi ) putchar('\n');
	printf( "City map #%d: %d camera(s) found\n", ++mi, cm );
	sort( cameras.begin(), cameras.end() );
	FOR( i, 0, cameras.size()-1 )
	cout << cameras[i] << endl;
	}
	return 0;
	}

view raw 10199 - Tourist Guide.cpp hosted with ❤ by GitHub