【UVa】208 Firetruck（dfs）

题目

题目

 

---

 

分析

一开始不信lrj的话，没判联通，果然T了。

没必要全部跑一遍判，只需要判断一下有没有点与n联通，邻接表不太好判，但无向图可以转换成去判n与什么联通。

关于为什么要判，还是因为数据造的强，造了许多之前的节点情况巨多，然而所有节点都不和终点连接的情况。。。。。。

 

---

 

代码

#include <bits/stdc++.h>

using namespace std;

int n;

vector<int> G[100];

vector<int> Ans;

int num=0;

bool vis[100];

bool dfs(int u)

{

	if(u==n)

	{

		printf("%d",Ans[0]);

		for(int i=1;i<Ans.size();i++) printf(" %d",Ans[i]);

		puts("");

		num++;

		return true;

	}

	for(int i=0;i<G[u].size();i++)

	{

		int v=G[u][i];

		if(vis[v]) continue;

		Ans.push_back(v);

		vis[v]=true;

		if(dfs(v)) Ans.pop_back();

		vis[v]=false;

	}

	return true;

}

int main()

{

	int t=0;

	while(scanf("%d",&n)==1 && n)

	{

		memset(vis,0,sizeof(vis));

		for(int i=0;i<30;i++) G[i].clear();

		Ans.clear();

		num=0;

		printf("CASE %d:\n",++t);

		int a,b;

		while(scanf("%d%d",&a,&b) && a && b)

		{

			if(a==b) continue;

			G[b].push_back(a);

			G[a].push_back(b);

		}

		int ok=0;

        for(int i=0;i<G[n].size();i++)

            if(G[n][i]) ok=1;

		G[0].push_back(1);

		for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());

		if(ok) dfs(0);

		printf("There are %d routes from the firestation to streetcorner %d.\n",num,n);

	}

	return 0;

}