Beyond the Void
BYVoid
USACO 4.3.3 Buy Street Race 街道賽跑 race3
本文正體字版由OpenCC轉換

一道基礎的連通分量的圖論題。這個題默認了0爲起點,N爲終點,如果不放心可以再讀入的時候判斷起點和終點,即入度爲0的點爲起點,出度爲0的點爲終點。

該題有兩問,第一問很簡單,可以嘗試去掉每一個點,判斷從起點到終點是否有通路,如果沒有則該點爲“必經點”。

第二問終點在於理解題意。首先可以確定第二問的解集是第一問的子集,所以我們可以第一問得出的每個點深搜,記錄下可以到達的點。然後去掉該點,從起點深搜。如果不存在兩次深搜皆可到達的點,就說明它是分割點。

/*
ID: cmykrgb1
PROG: race3
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 101
using namespace std;
ifstream fi("race3.in");
ofstream fo("race3.out");

int adjl[MAX][MAX];
int ans[MAX][2];
bool used[MAX],tused[MAX];
int N,start,end;

void init()
{
	int a=0,i=0;
	while (a!=-1)
	{
		fi >> a;
		while (a>=0)
		{
			adjl[i][ ++adjl[i][0] ]=a;
			used[a]=true;
			fi >> a;
		}
		i++;
	}
	N=i-2;
	for (i=0;i<=N;i++)
	{
		if (adjl[i][0]==0)
			end=i;
		if (!used[i])
			start=i;
	}
}

void dfs3(int i)
{
	int k,j;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!tused[j])
		{
			tused[j]=true;
			dfs3(j);
		}
	}
}

void dfs2(int i)
{
	int k,j;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!used[j])
		{
			used[j]=true;
			dfs2(j);
		}
	}
}

void question2()
{
	int i,j,k;
	for (i=1;i<=N-1;i++)
	{
		memset(used,0,sizeof(used));
		memset(tused,0,sizeof(tused));
		dfs2(i);
		tused[i]=true;
		tused[0]=true;
		dfs3(0);
		k=1;
		for (j=0;j<=N;j++)
			if (j!=i && used[j] && tused[j])
			{
				k=0;
				break;
			}
		if (k)
			ans[ ++ans[0][1] ][1]=i;
	}
}

void dfs1(int i)
{
	int k,j;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!used[j])
		{
			used[j]=true;
			dfs1(j);
		}
	}
}

void question1()
{
	int i;
	for (i=1;i<=N-1;i++)
	{
		memset(used,0,sizeof(used));
		used[i]=true;
		dfs1(0);
		if (!used[N])
			ans[ ++ans[0][0] ][0]=i;
	}
}

void print()
{
	int i;
	fo << ans[0][0];
	for (i=1;i<=ans[0][0];i++)
		fo <<' ' << ans[i][0];
	fo << endl;
	fo << ans[0][1];
	for (i=1;i<=ans[0][1];i++)
		fo <<' ' << ans[i][1];
	fo << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	question1();
	question2();
	print();
	return 0;
}

上次修改時間 2017-02-03

相關日誌