成立网站要什么手续,电信200m宽带做网站卡吗,wordpress访问满,国内公关公司排名problem
洛谷链接
solution
看到这个 20%20\%20% 的特殊性质#xff0c;脑海里第一个就想到了随机化算法。已经PTSD了着实上头
如果本题只是随便求一个 interesting\text{interesting}interesting 的点#xff0c;那就非常简单了。
随机化一个点#xff0c;检查这个点是…problem
洛谷链接
solution
看到这个 20%20\%20% 的特殊性质脑海里第一个就想到了随机化算法。已经PTSD了着实上头
如果本题只是随便求一个 interesting\text{interesting}interesting 的点那就非常简单了。
随机化一个点检查这个点是否满足 interesting\text{interesting}interesting 的限制即可。
如果判断一个点是否是 interesting\text{interesting}interesting 的点以该点为根建立 dfs-tree。如果只有树边和返祖边没有一条横叉边那么这个点就是“有趣点”。
一次判断的复杂度是 O(n)O(n)O(n) 的。
执行 min(100,n)\min(100,n)min(100,n) 次正确率就高达 1−(45)1001-(\frac{4}{5})^{100}1−(54)100。
虽然很简单但是本题的正解就是建立在这种随机的基础上的。
我们不能求出所有点但是可以快速通过随机求出一个 interesting\text{interesting}interesting 点记为 ididid。
以 ididid 为根建立 dfs-tree 那么这棵树是没有横叉边的。
考虑能否在这棵树上求出所有的 interesting\text{interesting}interesting 点。
显然是可以的需要用到几个小性质。
定理1 树上一个非根节点 uuu 的子树内至少会有一条连向子树外的边跨过 uuu即返祖边。
这是显然的因为题目保证点两两之间是可以互达的。
定理2 如果树上一个非根节点 uuu 的子树内有不止一条连向子树外的边则该点不是 interesting\text{interesting}interesting 点。
如果两条返祖边都指向同一个祖先也就意味着 uuu 有两条到达这个祖先的路径。如果两条返祖边指向不同的祖先但这两组先之间也存在祖先后辈关系相当于到某个辈分较小的祖先也有两条路径。
定理3 如果树上一个非根节点 uuu 的子树内只有一条连向子树外的边uuu 是“有趣点” 当且仅当这条返祖边连向的祖先也是“有趣点”。
这也是显然的。uuu 到这个祖先是一条简单路径祖先不是“有趣点”就意味着祖先到某个点有不止一条路径。传递过来等价于 uuu 到某个点也有不止一条路径。
请时刻注意根 ididid 一定是“有趣点”树一定没有横叉边。
所以我们可以通过 dfs 来完成筛选。
code
#include bits/stdc.h
using namespace std;
#define maxn 100005
bool flag;
int T, n, m;
vector int ans, G[maxn];
int dep[maxn], low[maxn], cnt[maxn], vis[maxn];
bool bad[maxn];void dfs_good( int u ) {if( ! flag ) return;vis[u] 1;for( int v : G[u] )if( ! vis[v] ) dfs_good( v );else if( vis[v] 2 ) { flag 0; return; }vis[u] 2;
}int dfs( int u ) {vis[u] 1, low[u] u;for( int v : G[u] )if( ! vis[v] ) {dep[v] dep[u] 1;cnt[u] dfs( v );if( dep[low[v]] dep[low[u]] ) low[u] low[v];}
//为什么选深度最小的点呢因为这个点的辈分最大 能跨过这个点的返祖边对应的点越少else {cnt[u] , cnt[v] --;//因为之前是直接把后代的返祖边加上来的但是这些返祖边对于这个祖先而言还是后代之间的连边 并未跨过这个祖先if( dep[v] dep[low[u]] ) low[u] v;}if( cnt[u] 1 ) bad[u] 1;return cnt[u];
}void dfs_bad( int u ) {vis[u] 1;if( bad[low[u]] ) bad[u] 1;for( int v : G[u] ) if( ! vis[v] ) dfs_bad( v );
}int main() {mt19937 wwl(time(0));scanf( %d, T );while( T -- ) {ans.clear();for( int i 1;i n;i ) {G[i].clear();low[i] bad[i] dep[i] cnt[i] vis[i] 0;}scanf( %d %d, n, m );for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );G[u].push_back( v );}uniform_int_distribution int range( 1, n );int id -1;for( int t 1;t 100;t ) {flag 1;for( int i 1;i n;i ) vis[i] 0;id range( wwl );dfs_good( id );if( flag ) break;}if( ! flag ) { puts( -1 ); continue; }for( int i 1;i n;i ) vis[i] 0;dfs( id );for( int i 1;i n;i ) vis[i] 0;dfs_bad( id );for( int i 1;i n;i )if( ! bad[i] ) ans.push_back( i );sort( ans.begin(), ans.end() );if( ans.size() * 5 n ) printf( -1 );else for( int i : ans ) printf( %d , i );printf( \n );}return 0;
}
