1077. Travelling Tours @ Timus Online Judge

大致题意就是一个无向图，让你找 $T$ 个环（环上点不能重复），要求每个环都至少含有一条边是其余边没有的，并且 $T$ 最大，然后让你输出这 $T$ 个环，有SPJ。

思路十分简单：

提示1：这道题目存在一个结论。

提示2：结论：一个 $n$ 个点 $m$ 条边的无向连通图一定有 $m-n+1$ 个环。

提示3：这道题的算法是 $DFS$ 加贪心算法。

提示4：考虑树加一条边变成一个环。

先证明一下结论：

考虑一个图的生成树，在树上加一条边就会变出一个环，这样就可以形成 $m-n+1$ 个环，但是这是不是上限呢？证明一下：

考虑已经选了 $T$ 个环，那么怎么选择 $T+1$ 个环呢，将环上不同于其他环的边称为特殊边，选新环即是在删掉了特殊边的原图上找环。在这之前证明一个性质：删掉特殊边不影响图的连通性。

先证明不破坏连通性的性质：如果删除了特殊边 $x,y$ ，假设 $tx,ty$ 连通性被破坏，因为环所以 $x,y$ 之间存在两条路径，则原来存在一条不经过 $x-y$ 的 $tx-x-y-ty$ 的路径，所以删除后连通性并没有被破坏，矛盾，证毕。

所以，我们假设现在有 $T$ 个环（ $T>m-n+1$ ），从中挑出 $m-n+1$ 个，删除掉其的特殊边，则剩余$n-1$ 条边，则图变成了一棵树，则不可能存在一个环，与 $T>m-n+1$ 矛盾，因此结论成立。

这样，这道题目就简单许多了，我们只需要暴力DFS就行了。

时间复杂度：$O(n+m+$环上点数的总和$)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<cstring>
#define N 210
#define M 41000
using namespace std;
struct node
{
	int y,next;
}a[M];int len=1,last[N];
inline void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
int n,m;
int fa[N];
int ans[1100000],ll[M],rr[M],cnt,top,dep[N];
inline void findans(int x,int y)/*x->y*/
{
	if(dep[x]<dep[y])return ;//上到下，下到上，防止重复
	cnt++;ll[cnt]=top+1;
	while(x!=y)
	{
		ans[++top]=x;
		x=fa[x];
	}
	ans[++top]=y;
	rr[cnt]=top;
}
void dfs(int x)
{
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa[x])
		{
			if(!dep[y])
			{
				fa[y]=x;dep[y]=dep[x]+1;
				dfs(y);
			}
			else
			{
				findans(x,y);
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dep[i])
		{
			dep[i]=1;
			dfs(i);
		}
	}
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)
	{
		printf("%d ",rr[i]-ll[i]+1);
		for(int j=rr[i];j>=ll[i];j--)printf("%d ",ans[j]);
		printf("\n");
	}
	return 0;
}

吐槽：

语文不好，请见谅。

你以为我很会这道题，TM我是看题解的。

TMD没做出来，怎么当时就一点都没有想到DFS树呢？为什么当时想的结论一个比一个奇葩呢？？？

。。。