题解 P7251 [JSOI2014] 强连通图
银河AI
·
·
题解
解题思路
task1 很简单，就是让求所有强连通分量中最大的 size，tarjan 模板。
接下来考虑 task2 ，一个强连通图有什么性质？入度和出度为 0。
我们可以根据这个性质推断，我们只要让缩点后的那个图，每个点的出度入度都为 0 就可以了。
我们可以先遍历原图的每一个点，处理缩点后的图的出度入度。
接下来我们用 sum1 来记录缩点后的图的入度为 0 的点的个数。
取 $sum1$ 和 $sum2$ 的最大值输出即可。
注意一个**特殊情况**：
当原图本身就是一个强连通图，即只有一个强连通分量的时候，直接输出`1 0`。
### AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,M=3e5+1;
int n,m;
struct edge{
int to,ne;
}e[M];
int adj[N],l;
inline void add(int x,int y){e[++l].to=y,e[l].ne=adj[x],adj[x]=l;}
int dfn[N],low[N],vis[N],st[N],si[N],bel[N],oud[N],ind[N];
int cnt,le,top;
void dfs(int x){
dfn[x]=low[x]=++cnt;
vis[x]=1;
st[++top]=x;
for(int i=adj[x];i;i=e[i].ne){
int y=e[i].to;
if(!dfn[y]) dfs(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
le++;
while(top){
int nx=st[top--];
vis[nx]=0;
si[le]++;
bel[nx]=le;
if(nx==x) break;
}
}
}
int maxn,ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
if(le==1){printf("1\n0");return 0;}
for(int i=1;i<=le;i++) maxn=max(maxn,si[i]);
printf("%d\n",maxn);
for(int i=1;i<=n;i++){
int x=i;
for(int j=adj[x];j;j=e[j].ne){
int y=e[j].to;
int fx=bel[x],fy=bel[y];
if(fx!=fy) oud[fx]++,ind[fy]++;
}
}
int sum1=0,sum2=0;
for(int i=1;i<=le;i++){
if(!ind[i]) sum1++;
if(!oud[i]) sum2++;
}
printf("%d",max(sum1,sum2));
}
```