2.种树(tree.pas/cpp/in/out)

问题描述：

Fanvree 很聪明，解决难题时他总会把问题简单化。

例如，他就整天喜欢把图转化为树。但是他不会缩环，那他怎么转化呢？这是一个有

n 个点 m 条双向边的图，Fanvree 会选定一个节点，然后删掉这个节点和这个点连出去的边，

如果变成了一棵树，那么这个节点便是可行的，什么是树呢？树也即无简单环的无向连通图。

告诉 Fanvree 可能的节点是什么。

输入：

第一行两个正整数 n 和 m，表示有 n 个点 m 条边，保证 n≥2。

接下来 m 行，每行两个整数 v,u，表示 v 和 u 之间有一条无向边 1≤v,u≤n，保证没

有重边和自环。

输出：

第一行一个正整数 ns，表示这个图中有 ns 个结点可选。

接下来一行，共 ns 个整数，每个整数表示一个可选结点的编号。

请按编号从小到大的顺序输出。

数据保证图中至少存在一个可选的结点。

样例输入：

样例输出：

3

4 5 6

数据范围：

对于 40%的数据：n，m<=1000；

另外存在 10%的数据：m=n-1；

另外存在 20%的数据：m=n；

对于 100%的数据：n，m<=100000。

写在前面

只要掌握一个小定理，就显得十分简单（啊呸，叫我这种刚刚普及退役\(Tarjan\)都不会蒟蒻找割点）

当且仅当一个有N个节点的连通图有N - 1条边，这是一棵树。

思路

输入时，记录每个点相连的边数s。

如果 M - s[P] != N - 2，该图不满足前面提到的定理，删去P不是一棵树。

如果该点为割点，那么删去P将不连通。

所以预处理出割点、每个点相连的边数即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout );

#define MAXN 100005

#define MAXM 100005

int n, m, ans;

int hd[MAXN], nxt[MAXM << 1], to[MAXM << 1], s[MAXN], tot(1);

void Add( int x, int y ){ nxt[++tot] = hd[x]; to[tot] = y; hd[x] = tot; }

int dfn[MAXN], low[MAXN], num, root;

bool cut[MAXN];

void Tarjan( int x ){ //找割点——

	dfn[x] = low[x] = ++num; int cnt(0);

	for ( int i = hd[x]; i; i = nxt[i] ){

		if ( !dfn[to[i]] ){

			Tarjan(to[i]);

			low[x] = min( low[x], low[to[i]] );

			if ( dfn[x] <= low[to[i]] ) cnt++;

		} else low[x] = min( low[x], dfn[to[i]] );

	}

	if ( cnt && ( x != root || cnt > 1 ) ) cut[x] = 1;

}

int main(){

	open("tree");

	scanf( "%d%d", &n, &m );

	for ( int i = 1; i <= m; ++i ){

		int x, y; scanf( "%d%d", &x, &y );

		Add( x, y ), Add( y, x ); s[x]++; s[y]++;

	}

	root = 1; Tarjan(1);

	//别忘了 如果图是由一棵树和一个孤零零的点组成。。。

	if ( num == 1 ){ //不连通的话，如果找到的点只有1个(节点1)，那只有可能节点1是满足要求的点

		root = 2; Tarjan( 2 );

		if ( num == n && m == n - 2 ) printf( "1\n1\n" );

		return 0;

	}

	if ( num == n - 1 ){ //如果找到的点有n - 1个，那么在非节点1的节点中有一个还满足题要求。。。

		if ( m == n - 2 ){

			printf( "1\n" );

			for ( int i = 2; i <= n; ++i )

				if ( !dfn[i] ){ printf( "%d\n", i ); break; }

		}

		return 0;

	}

	if ( num != n ){ printf( "0\n0\n" ); return 0; } //如果有多个点不能到达，咋删都成不了棵树。。。 

	for ( int i = 1; i <= n; ++i ) if ( m - s[i] == n - 2 && !cut[i] ) ans++; //边数符合、不是割点，它一定是棵树！

	printf( "%d\n", ans );

	for ( int i = 1; i <= n; ++i ) if ( m - s[i] == n - 2 && !cut[i] ) printf( "%d ", i );

	return 0;

}

巴特西

「2018-12-02模拟赛」T2 种树解题报告

2.种树(tree.pas/cpp/in/out)

问题描述：

输入：

输出：

样例输入：

样例输出：

数据范围：

写在前面

思路

代码

最新文章

热门文章

巴特西

「2018-12-02模拟赛」T2 种树 解题报告

2.种树(tree.pas/cpp/in/out)

问题描述：

输入：

输出：

样例输入：

样例输出：

数据范围：

写在前面

思路

代码

最新文章

热门文章

「2018-12-02模拟赛」T2 种树解题报告