ZROI#1006

你的名字 2023-06-02 12:52 14阅读 0赞

[ZROI\#1006][ZROI_1006]

可能一眼看起来是个很不可做的题,但你仔细思考一下,你发现.....给的是个\\(n\\)个点\\(n\\)条边的东西...  
那么它可能是个啥呢?  
是个基环树?是个森林+环?是个基环树+森林?  
都是有可能的!  
然后我们发现,答案就是连通块个数+环数-1.  
为什么呢?  
假设有\\(x\\)个连通块,\\(y\\)个环,那么对于连通块我们一定有一个作为答案连通块,其余的都要接在这下面,且只需修改根即可,所以连通块对答案的贡献是\\(x-1\\),而对于环,必须拆开,且只需要断开一处成为链接在答案连通块之下即可,所以环的贡献是\\(y\\).

可得答案即为\\(x+y-1\\).

\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define one first #define two second #define rint read<int> #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e5 + 100 ; struct edge { int to , next ; } e[N] ; int head[N] , tot ; int n , f[N] , ans , cnt , in[N] , siz = 0 ; queue < int > q ; bool vis[N] , founded ; inline void build (int u , int v) { e[++tot].next = head[u] ; head[u] = tot ; e[tot].to = v ; } inline void topsort () { rep ( i , 1 , n ) if ( ! in[i] ) q.push ( i ) ; while ( ! q.empty () ) { int j = q.front () ; q.pop () ; vis[j] = true ; for (int i = head[j] ; i ; i = e[i].next) { int k = e[i].to ; -- in[k] ; if ( ! in[k] ) q.push ( k ) ; } } return ; } inline void dfs (int cur) { vis[cur] = true ; ++ siz ; for (int i = head[cur] ; i ; i = e[i].next) if ( ! vis[e[i].to] ) dfs ( e[i].to ) ; return ; } int main (int argc , char * argv[]) { n = rint () ; rep ( i , 1 , n ) { f[i] = rint () ; build ( i , f[i] ) ; ++ in[f[i]] ; } topsort () ; rep ( i , 1 , n ) if ( ! vis[i] ) { siz = 0 ; dfs ( i ) ; if ( siz == 1 && ! founded ) founded ^= 1 ; else ++ ans ; } printf ("%d\n" , ans ) ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11572101.html

[ZROI_1006]: http://www.zhengruioi.com/problem/1006