太空战队
- 总时间限制:
- 1000ms
- 内存限制:
- 131072kB
- 描述
-
在社会经济高速发展的今天，借助高科技手段，组建太空战队的愿望就快实现了。
战队属下有N个航天员。作为空军选拔上来的佼佼者，每个航天员都有与生俱来的骄傲——他们每个人都认为自己是最强的或者是第二强的。这样，如何分组就成了司令官的难题了。司令官分组的方法是这样的：
步骤1:任意选择一个未被分组的航天员，记为当前航天员.
步骤2:把当前航天员分入一个新的组.
步骤3:如果当前航天员心目中最强的那个航天员（记为Q航天员）还没有被分组，那么把Q航天员分入当前航天员所在组，并把Q航天员作为当前航天员并重复步骤3；如果Q航天员已经被分组，那么重复步骤1，直至所有航天员都被分入了某个组。
司令官想请你帮忙计算：按上面的分组方式，最多/最少能分成几个组
分析：
先用样例构图，是一个带“把”的环。因为每个人都很单纯，只连一个向外的边，因此这个图就可以由若干个头尾或相接或不相接的环以及点构成。
先想最小怎么办，看图，可以发现只要用手提起一条“链”的首端，整条链都可以提起来。因此它就转换成了求图中能提起一个带起一串的“链”的个数，也就是联通分量的个数。
再想最大怎么办，看图，发现2、3、4无论从谁开始都得拉出三个人。因此不能把这三个人破开。而一但我们把这个环先处理掉（即把它分好组），那么1就只好一个人孤零零一组了。因此就转化成了求图中强连通分量的个数。
实现：
实现时我们反着来，先找出图中强连通分量，并一定要记录每个人都在哪一个组，第一问就好了。接着，我们通过寻找任意两个强连通分量的联系，把在一个强连通分量中的点缩成一个点，接着我们只需寻找有多少入度为0的缩点。
参考代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <stack> using namespace std; stack<int> q; int map[100010]; int dfn[100010],low[100010],visit[100010],p[100100]={0}; int be[100010]={0}; int n,m,ncon,a,b,indx=0; void clear() { while(!q.empty()) q.pop(); } void init() { memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(visit,0,sizeof(visit)); for(int i=1;i<=m;i++) map[i]=0; ncon=indx=0; } void set_tree() { for(int i=1;i<=m;i++) { cin>>b; map[i]=b; } } void dfs(int root) { visit[root]=2; dfn[root]=low[root]=++indx; q.push(root); int t=map[root]; if(visit[t]==0) { dfs(t); low[root]=min(low[root],low[t]); } else if(visit[t]==2) low[root]=min(low[root],dfn[t]); if(low[root]==dfn[root])//no child { ncon++; while(!q.empty()) { int j=q.top(); q.pop(); visit[j]=1; be[j]=ncon; if(j==root) break; } } } void solve() { for(int i=1;i<=m;i++) if(!visit[i]) dfs(i); int ans=0; for(int i=1;i<=m;i++) if(be[i]!=be[map[i]])//缩点 p[be[map[i]]]++;//MARK!!!! for(int i=1;i<=ncon;i++) if(p[i]==0) ans++; cout<<ncon<<" "<<ans; } int main() { cin>>m; init(); set_tree(); solve(); return 0; }
注意“MARK!!!!”的地方，在找到两个相连但却不在同一强连通分量的点后，第一感觉是“两个点是可以互换的，标记谁都行”（标记即意味着该点所代表的强连通分量要删去，在两个相连的点中只保留一个组），但经过调试，发现不行。只能标记当前点所指向的那个点，不能标记自己，否则会多标记。因为你不能保证当前点有入度，（这里意思是：在缩点过程中，只保留那个入度为零的点作为此强联通分量的代表，因为这个点不可能再被别的点标记，如果一个强联通分量没有入度为0的点，也就是一个环，那么它要不被别的强连通分量所吞并，要么独成一体，也不可能被标记，因此不作特殊处理）如果你标记了当前点，很可能你就把一个入度为0的强连通分量标记了。